13.5.Еще пример задания

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх вниз влево вправо.

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:

сверху свободно снизу свободно

слева свободно справа свободно

Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку.

Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену)?

1) 1 2) 13 3) 21 4) 39

НАЧАЛО

ПОКА вниз

ПОКА влево

вверх

вправо

КОНЕЦ

Решение:

1. нарисуем примерный путь Робота в соответствии с программой; вот три варианта, когда Робот не разбивается:

здесь ключевые клетки – две стенки (слева и снизу) и три ярко-зеленых клетки, которые должны быть свободны

1. теперь ищем на карте участки, где есть все ключевые клетки (они выделены на рисунке):

обратите внимание, что в двух случаях нижняя «ключевая» стенка имеет длину больше 1 (темно-коричневый цвет), то есть Робот может спускаться по разным линиям.

1. теперь осталось подсчитать все клетки, спускаясь из которых Робот упирается в темно-коричневые стенки:

1. подсчет показывает, что их 39 штук;

2. поэтому правильный ответ – 4.