Решение: Закрашивание клеток у стен
На бесконечном поле есть горизонтальная и вертикальная стены. Правый конец горизонтальной стены соединён с нижним концом вертикальной стены. В каждой стене есть ровно один проход, точное место прохода и его ширина неизвестны. Робот находится в клетке, расположенной непосредственно над горизонтальной стеной у её левого конца. Напишите алгоритм, закрашивающий все клетки, расположенные непосредственно выше горизонтальной стены и левее вертикальной стены. Проходы должны остаться незакрашенными. Робот должен закрасить только клетки, удовлетворяющие данному условию. Алгоритм должен работать для любого допустимого расположения стен и любых проходов.
Решение по шагам
4 шагаАлгоритм состоит из двух частей. Сначала Робот движется вправо по клеткам непосредственно над горизонтальной стеной. Клетки над стеной закрашиваются, но перед проходом Робот останавливается, поэтому клетка прохода не закрашивается.
Через проход в горизонтальной стене Робот спускается вниз, затем движется вправо под горизонтальной стеной до нижнего конца вертикальной стены.
Далее Робот поднимается вдоль вертикальной стены. Клетки слева от стены закрашиваются. Если встречается проход в вертикальной стене, Робот проходит вокруг него по свободным клеткам и возвращается на левую сторону стены, не закрашивая клетки прохода.
Один из допустимых вариантов записи алгоритма с использованием вспомогательных алгоритмов:
Алгоритм должен последовательно найти проход в горизонтальной стене, пройти к нижнему концу вертикальной стены и закрасить клетки вдоль её левой стороны, обходя единственный проход. В результате закрашенными остаются только клетки непосредственно выше горизонтальной стены и непосредственно левее вертикальной стены.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Закрашивание клетки прохода в горизонтальной или вертикальной стене.
Попытка пройти сквозь стену без предварительной проверки свободного направления.
Остановка при первом проходе вместо обхода прохода в вертикальной стене.
Закрашивание клеток, не расположенных непосредственно у нужной стены.