Исполнитель Робот умеет перемещаться по… (информатика)

Алгоритм для Робота: проход через стену с неизвестным проходом

Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости, разбитой на клетки. Между соседними (по сторонам) клетками может стоять стена, через которую Робот пройти не может. Робот находится в левом нижнем углу огороженного пространства, имеющего форму прямоугольника. Размеры прямоугольника неизвестны. Где-то посередине прямоугольника есть вертикальная стена, разделяющая прямоугольник на две части. В этой стене есть один проход, при этом проход не является самой верхней или самой нижней клеткой стены. Точное расположение прохода неизвестно. Составьте алгоритм для Робота, перемещающий Робота в правый верхний угол прямоугольника. При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться.

Шаблон алгоритма: три пустые команды; затем пять циклов «нц пока … кц» (в каждом одно условие и одна команда внутри); «кон».

Решение

Проход не в верхней и не в нижней клетке стены, значит, в прямоугольнике не меньше строк. Поэтому первые две команды «вверх» безопасны.

Три первые команды: вверх, вниз, вверх (Робот поднимается на клетку, лишь бы не врезаться).

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

Алгоритм:

вверх
вниз
вверх
нц пока снизу свободно
  вниз
кц
нц пока справа свободно
  вправо
кц
нц пока справа стена
  вверх
кц
нц пока справа свободно
  вправо
кц
нц пока сверху свободно
  вверх
кц
кон

💡 Почему так

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

Ответ

✓ dzmen.ru

Первые три команды: вверх, вниз, вверх.
Пять циклов по порядку:

нц пока снизу свободно — вниз
нц пока справа свободно — вправо
нц пока справа стена — вверх
нц пока справа свободно — вправо
нц пока сверху свободно — вверх
кон

Помогло?

Исполнитель Робот умеет перемещаться по лабиринту, начерченному на плоскости…