На поле Робота ровно одна стена. Это горизонтальная стена, которая не примыкает к границам поля. Робот находится в одной из клеток, прилегающих к стене сверху. Точные размеры поля и стены и точное расположение Робота неизвестны. Составь алгоритм, при выполнении которого Робот:
а) окажется в одной из клеток, прилегающих к стене снизу;
б) закрасит все клетки, прилегающие к стене снизу;
в) закрасит все прилегающие к стене клетки.
Стена горизонтальна, поэтому двигаться вдоль неё вправо и влево можно свободно. Чтобы найти её конец, проверяем наличие стены снизу или сверху. Поскольку стена не примыкает к границам поля, клетка за каждым её концом существует и позволяет обойти стену.
а) Идём вправо, пока снизу стена. Как только снизу станет свободно, Робот находится за правым концом стены. Шаг вниз переводит его на нижнюю сторону, а шаг влево — в клетку непосредственно под последним участком стены.
алг перейти под стену
нач
нц пока снизу стена
вправо
кц
вниз
влево
кон
Отказа нет: вдоль стены вертикальных препятствий нет, вниз идём уже за концом стены, а влево — в существующую клетку под ней. Цикл заканчивается, потому что длина стены конечна.
б) Сначала выполняем алгоритм пункта а). Теперь над Роботом стоит стена. Закрашиваем клетки под ней справа налево, включая первую и последнюю.
алг закрасить под стеной
нач
перейти под стену
нц пока сверху стена
закрасить
влево
кц
кон
Закрашивание стоит перед движением: поэтому первая клетка под правым концом не пропускается. Из последней клетки под левым концом Робот выйдет ещё на одну клетку влево; там сверху свободно, цикл завершится. Эта внешняя клетка не закрашивается, поскольку условие проверяется перед закрашиванием.
в) Используем результат пункта б): Робот оказался сразу слева от стены, на уровне её нижней стороны. Поднимаемся вверх и шагаем вправо — это первая клетка над левым концом стены. Затем закрашиваем верхние прилегающие клетки слева направо.
алг закрасить обе стороны стены
нач
закрасить под стеной
вверх
вправо
нц пока снизу стена
закрасить
вправо
кц
кон
Шаг вверх выполнен за левым концом, поэтому через стену Робот не проходит. Верхний цикл заканчивается за правым концом. В каждом цикле Робот движется в одну сторону вдоль конечной стены, поэтому зацикливания нет. В результате закрашены все клетки, имеющие со стеной общую сторону, снизу и сверху.
а) Пока снизу стена, идти вправо; затем вниз, влево.
б) Выполнить а); пока сверху стена, закрасить и идти влево.
в) Выполнить б); затем вверх, вправо; пока снизу стена, закрасить и идти вправо.
