Хабы: Занимательные задачки, Алгоритмы, Математика
Задача
Дан связный прямоугольный лабиринт клеток, одна из которых обозначена как выход. В произвольной клетке появляется черепаха, и она может перемещаться в четырех направлениях (вверх, вправо, вниз, влево).
Черепаха не мыслит логически, однако имеет безупречную память. Она может запомнить и выполнить любую конечную последовательность команд. Черепаха не может перемещаться сквозь стенки лабиринта, и поэтому просто игнорирует команду, если не может ее исполнить и переходит к следующей.
Как только черепаха оказывается в клетке "выход", она тут же выходит из лабиринта и больше не исполняет никакие команды.
Расположение стенок лабиринта и клетки "выход" известны заранее, а вот начальное расположение черепахи неизвестно.
Помогите черепахе выбраться из лабиринта. Напишите конечную последовательность команд (up, right, down, left), которая гарантирует ей выход независимо от ее начального местонахождения.
Читать далее