Комментарии 12
Предположим, что мы начинаем в (0, 0). Добавим в строчку-ответ кратчайший путь от (0, 0) до выхода (найденный поиском ширину).
Предположим, что мы начинаем в (0, 1). Промоделируем уже набранный ответ начиная с этой клетки. Окажемся где-то. Добавим в строчку-ответ кратчайший путь от этого места до выхода (найденный поиском ширину).
И так далее.
Комментатор ниже дельно предложил — найти минимальную строку. Еще бы хотелось маршрут, где робот не будет касаться барьеров или доказать, что такого алгоритма нет
А* будет эффективней чем BFS.
Как он может быть эффективнее, если вам нужно путь из каждой клетки узнать? Да и вообще время решения исходит не из линейного BFS, а от набора/эмуляции решения. Но как по мне рандомизированное решение практичнее.
Еще бы хотелось маршрут, где робот не будет касаться барьеров или доказать, что такого алгоритма нет
Если под барьером вы понимаете ситуацию, когда робот, получив команду, останется на месте, так как там стена, то маршрута из любой произвольной точки нет.
Достаточно представить, что робот начинает из крайних правой, левой, верхней и нижней точек. Для любой команды будет положение, в котором робот останется на месте.
Теперь руки чешутся написать алгоритм нахождения минимальной строки для заданного лабиринта.
Простая конкатенация не даст минимальную строку. Пять команд влево выведут к финишу из 5 ячеек справа от него. При конкатенации понадобилось бы написать 15 команд влево (1 — для первой ячейки, 2 — для второй и т.д.)
Стоит смотреть алгоритмы синхронизации конечных автоматов, так как описание задачи практически одинаково: Для заданного КА найти последовательность команд, переводящую КА из произвольного состояния в одно определенное.
Когда робот наступает на выход к его координате присуммируется заведомо большое число, такое что робот вылетает за границы массива, что можно отловить как ошибку с помощью блока:
try # если здесь произошла ошибка catch # то выполняются действия из этого поля end
Охх, какая кулебяка получается :) Что показывает, как далеко отстоит спортивное программирование от промышленного…
Нет, это, наверное, не плохо для ОЛИМПИАДНОГО примера отлавливать завершение работы исключением, но если такое в промышленный код внедрить — уже, извиняюсь, решение не фонтан:
1) Инструмент используется не по назначению. Страдает стиль и читаемость кода
2) А что, если в коде закрадется ошибка, которая приведет к ровно тому же исключению?
Конечно же этот вариант был предложен для прикола, чтобы упомянуть блок трай-кеч, а так нормальные люди просто зададут функцию isexit(point)::bool
Хотя, конечно, ловить все исключения — это жесть, да, согласен…
Джулия в лабиринте