Какой тест не проходит решение?

Question

[BitNeBolt]

Решаю эту задачу, но не могу пройти 11-й тест. Решение проверял не разных случаях: когда выход достижим, когда к нему короче добраться через портал, когда без портала, когда есть путь через несколько подряд идущих порталов, когда портал приводит в зону, в которой находится выход, но в которую нельзя попасть из-за стен.

Переполнения быть не должно, так как уже стал использовать BiInteger (пишу на джаве).

Какой еще вариант стоит проверить?

Comments

[Василий Банников]

А пробовал вариант, когда портал тоже запускает за стену, через которую невозможно к цели попасть?
А когда вход в портал не достижим?
Какой вообще алгоритм для поиска пути используешь?
А когда комбинация из разных параметров одновременно на разных выходах?

Попробуй использовать техники тест-дизайна чтобы полностью покрыть свой код тестами.

[BitNeBolt]

Василий Банников, первый - да, второй - нет. Про тестирование почитаю, посмотрю подробнее.

Использую по сути волновой алгоритм.

[Wataru]

BitNeBolt, Волновой алгоритм может работать медленно. Введите ему тест -спираль размера 100x100. Ну, или стены в шахматном порядке и порталы из каждой клетки в следующую по порядку. Начало - в левом верхнем углу, выход - в правом нижнем.

Если его соптимизировать, то получится самый обычный обход в ширину.

Answer 1

[Wataru]

Простейшая задача на bfs. Без кода сложно сказать, где накосячено.

Никакого переполнения быть не может, bigInteger вам не нужен. Даже long не нужен: максимальная длина пути - 10000.

Comments

[BitNeBolt]

О переполнении задумался от безысходности) до сих пор понять проблему не получалось

[Wataru]

BitNeBolt, Опечатка какая-нибудь где-нибудь. Давайте код.

[BitNeBolt]

Wataru, тут все очень стрёмно: от хранения расстояния до каждого выхода, до использования отдельной структуры для описания вершины, ещё и МАХ в глаза бросается...

spoiler

А всё :)

[Wataru]

BitNeBolt, Все очень запутанно. Перепишите без длинной арифметики. И хранение расстояние внутри Point - очень плохое решение.

Вам нажно лишь несколько матриц NxM. Одна - для хранения стен. Одна - для пометки, что точка - выход. Две - для пометок координат выхода из тоннеля. Одна - для хранения расстояния до клетки, Одна для пометок visited.

Надо помечать вершину visited при помещении ее в очередь, а не при доставании оттуда.

Еще, вы вершину в очередь пихаете перед увеличением расстояния на 1, а надо после.

И проще ваш bfs сделать возвращающим ответ к задаче (или -1) - когда вы из очереди достали координаты клетки с выходом - можно сразу выходить и возвращать расстояние до нее. Если обработали всю очередь - возвращайте -1.

[BitNeBolt]

Wataru, с недавних пор в java появились записи - структуры для хранения нескольких значений. Они могут объявляться в одну строчку (здесь в самомо начале о них кратко говорится https://m.habr.com/ru/post/538800/).

Если они итак должны использоваться (не иметь же две очереди для каждой координаты), то стоит ли использовать Map для хранения значений или же лучше не лениться и прописать массивы и обращаться к ним по индексам (координаты, хранящиеся в пойнт)? Первое требует гораздо меньше кода.

На acmp как раз пару дней назад начали использовать 16ую джаву.

[Wataru]

BitNeBolt, Нет, мапы вам тут не нужны, раз отлично подходят массивы. Ну храните выходы из портала не в двух массивах, а в одном массиве point. Не понимаю, как мап будет короче.

[Wataru]

BitNeBolt, И я придумал тест - поле 2x2 без стен. Вход и выход в противоположных углах. Есть портал из входа в выход.

Проблема именно в том, что вы помечаете вершины при доставании из очереди, а не при помещении туда.

Тогда получается что вы в очередь поместите 2 соседних угла, потом выход (по порталу). Потом, обрабатывая 2 соседних угла, вы в очередь опять положите выход, но с расстоянием 2. И потом дойдя до этой записи в очереди вы перезапишете правильный ответ "1 шаг" на "2 шага".

Еще это можно пофиксить, если вывалится из цикла/функции bfs как только вы достали из очереди любой выход. Но это костыль на самом деле. Лучше не дублировать вершины в очереди.

Answer 2

[Rsa97]

Задача сводится к построению графа и нахождению кратчайшего пути в нём.
Каждый отсек, в котором нет стены, это узел графа.
Каждый возможный переход между отсеками, как в соседние, так и через гипертуннель, это ребро графа.