Черепаха в лабиринте: Медлительное путешествие к свободе

Задача

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

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

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

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

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

Читать далее