Привет, Хабр!

Прошел ровно год с момента публикации разбора задачи про красные и синие точки, и вот я снова нашел время, разобрать ещё одну увлекательную задачу. Надеюсь, вам понравится!

Задача

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

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

Как только черепаха оказывается в клетке "выход", она тут же выходит из лабиринта и больше не исполняет никакие команды.

Расположение стенок лабиринта и клетки "выход" известны заранее, а вот начальное расположение черепахи неизвестно.

Помогите черепахе выбраться из лабиринта. Напишите конечную последовательность команд (up, right, down, left), которая гарантирует ей выход независимо от ее начального местонахождения.

Например, для черепахи изображенной на рис. 1 подойдет последовательность: down, left, left, up, right, up, up, up, up, left, down, left, up. Однако, легко убедиться, что данная последовательность не подойдет, если начальное положение черепахи будет передвинуто, например, в нижний левый угол.

Вы не знаете начальное расположение черепахи. Ваша последовательность команд должна быть универсальной, то есть, выводить черепашку из лабиринта независимо от ее начальной позиции.

Вам на вход дается лабиринт с клеткой "выход". Гарантируется, что лабиринт связный: от любой клетки возможно дойти до любой другой.

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

Решение

Первая попытка решить

Давайте для каждой клетки составим маршрут, приводящий черепаху к выходу. Поскольку клеток, в которых может находиться черепаха конечное число, а именно , то просто выпишем все такие маршруты и будем перебирать их в любом порядке.

Если черепаха прошла по маршруту и не нашла выход, то продолжим перебирать варианты, предварительно вернувшись на исходную позицию, отменив команды справа налево. Например, для маршрута right, up, left сначала отменим третье действие - выполним right, затем второе - выполним down, затем первое - выполним left. Таким образом получим новую последовательность right, down, left.

Все классно, да? Но есть одно но.

Рассмотрим черепашку на рис. 2. Пусть у нее была последовательность, состоящая из одной единственной команды right. В этом случае, черепашка упрется в стенку справа, поэтому ничего не сделает. Однако, если мы попытаемся отменить данную операцию, то мы должны будем попросить черепаху пойти влево (выполнить left), что приведет ее совсем не туда, откуда она начинала.

Таким образом, мы на самом деле не умеем отменять ходы и возвращать черепаху на исходную позицию, что ломает нам нашу первую попытку и мы терпим неудачу.

Работа над ошибками

В первой попытке мы все же поняли кое-что важное: для каждой клетки лабиринта можно выписать путь к выходу.

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

Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте. Но, где именно она может находиться?

На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из клеток, но проделав данный маршрут она могла перейти в одну из клеток, если не вышла. Таким образом, количество вариантов нового расположения как минимум на 1 меньше, чем было изначально.

На рисунке 3 изображено, что примерно произошло в терминах теории множеств. Слева - множество клеток до выполнения набора команд, справа - после. Синими точками обозначены клетки, в которых теоретически может находиться черепаха. Как можно видеть, за счет того, что как минимум одна синяя точка (клетка) гарантированно переходит в клетку "выход", справа появится как минимум одна белая точка (клетка, в которую нас никогда не приведет данная последовательность команд).

На этом этапе вы, возможно, уже догадались, к чему я клоню :)

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

Любопытный факт: черепахи могут голодать по несколько месяцев. Их организм приспособлен к таким условиям благодаря медленному метаболизму :)

Заключение

Спасибо, что дочитали до конца. Если вам понравилось, нажмите стрелочку вверх, это действительно мотивирует меня продолжать делиться с вами интересными задачами и их разборами.