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