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

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

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

Шаблон алгоритма (в каждом пустом поле нужно выбрать команду или условие):
три пустые строки,
нц пока ... / команда / кц — пять таких циклов подряд,
кон

Решение

Проход не в самой верхней и не в самой нижней клетке стены, поэтому идём так: сначала в верхний левый угол, затем вдоль верхней стороны до стены, вдоль стены вниз до прохода, через проход до правой стенки и вверх в угол.

Видно только шаблон без списка вариантов в полях, поэтому первые три строки заполнены безопасными командами. Высота не меньше клеток, поэтому два шага вверх возможны. Эти строки на результат не влияют.

Три первые строки: вверх, вверх, вниз.
Цикл : Робот поднимается до верхней стенки.
Цикл : Робот идёт вправо до вертикальной стены. Он упрётся в неё в верхней строке, потому что проход не в самой верхней клетке.
Цикл : Робот идёт вниз, пока справа стена. Он остановится у прохода. Проход не в самой нижней клетке, поэтому Робот не упрётся в нижнюю стенку.
Цикл : Робот идёт вправо через проход до правой стенки.
Цикл : Робот идёт вверх до верхней стенки, то есть в правый верхний угол.

Заполненный шаблон:

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

💡 Почему так

Цикл «нц пока условие … кц» повторяет команду, пока условие истинно. Условия выбраны так, чтобы Робот не упёрся в стену. Подъём в верхний ряд гарантирует, что он дойдёт до стены, а так как проход не крайний, поиск прохода сверху вниз всегда завершится.

Ответ

✓ dzmen.ru

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

Помогло?

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