3. Выполните задание. На бесконечном поле есть горизонтальная и вертикальная стены. Левый конец горизонтальной стены соединен с верхним концом вертикальной стены. Длины стен неизвестны. В каждой стене есть ровно один проход, точное место прохода и его ширина неизвестны. Робот находится в клетке, расположенной непосредственно под горизонтальной стеной у ее правого конца. На рисунке указан один из возможных способов расположения стен и Робота (Робот обозначен буквой «Р»). Напишите для Робота алгоритм, закрашивающий все клетки, расположенные непосредственно ниже горизонтальной стены и правее вертикальной стены. Проходы должны остаться незакрашенными. Робот должен закрасить только клетки, удовлетворяющие данному условию. Например, для приведенного рисунка Робот должен закрасить следующие клетки (см. рис.). При исполнении алгоритма Робот не должен разрушиться, выполнение алгоритма должно завершиться. Конечное расположение Робота может быть произвольным. Алгоритм должен решать задачу для любого допустимого расположения стен и любого расположения и размера проходов внутри стен.

Алгоритм для Робота:

Задача: Закрасить клетки ниже горизонтальной стены и правее вертикальной стены, не закрашивая проходы.

Начальное положение робота: под горизонтальной стеной, у ее правого конца.

Общий подход: Робот должен исследовать область, двигаясь так, чтобы оставаться под горизонтальной стеной и двигаться вправо, пока не достигнет правой границы области. Затем он должен двигаться вниз, закрашивая клетки, пока не встретит нижнюю границу или проход в вертикальной стене.

1. Движение вправо:
• Пока робот не упрется в вертикальную стену (или не пройдет ее правый край, если он находится в проходе):
• Если робот находится в клетке, которую нужно закрасить (т.е. под горизонтальной стеной и правее вертикальной стены), закрасить ее.
• Двигаться на 1 клетку вправо.
2. Движение вниз:
• Если робот находится в клетке, которую нужно закрасить, закрасить ее.
• Двигаться на 1 клетку вниз.
3. Повторение:
• Когда робот достигнет нижней границы, он может остановиться.
• Если робот встречает проход в стене, он должен попытаться его обойти или пропустить (не закрашивать).
• Для гарантии обхода проходов, робот может использовать алгоритм "обхода стены справа" (или слева), если он попадает в тупик или на границу недоступной области.

Более детальный алгоритм (с учетом проходов):

1. Шаг 1: Исследование горизонтальной границы.
• Находясь под горизонтальной стеной, двигаться вправо.
• Если клетка непосредственно перед роботом свободна (проход), попробовать зайти в проход и продолжить движение вправо. Если это невозможно (проход слишком узок или робот застрял), вернуться и продолжать двигаться вдоль границы.
• Если клетка непосредственно перед роботом — стена, то робот находится у правой границы (или в проходе, если он там).
2. Шаг 2: Закрашивание и исследование вертикальной границы.
• Когда робот достиг правой границы (или вошел в проход вертикальной стены):
• Если клетка, где находится робот, должна быть закрашена, закрасить ее.
• Двигаться вниз.
• Если клетка, где находится робот, должна быть закрашена, закрасить ее.
• Если робот упирается в нижнюю стену или проход:
• Если это проход, попробовать его обойти (например, вернуться и двигаться вправо, если это возможно, чтобы найти другой путь или обойти проход).
• Если это нижняя стена, робот закончил закрашивание данной полосы.
• Повторять движение вниз, пока не будет достигнута нижняя граница или обнаружен проход.
3. Шаг 3: Перемещение для следующей полосы (если необходимо).
• Если робот должен закрасить следующую область (например, если он обнаружил, что есть еще незакрашенные клетки правее или ниже), он должен переместиться в начальную позицию для следующей полосы.
• Это может потребовать движения влево или вверх, чтобы вернуться под горизонтальную стену и найти новую стартовую точку для закрашивания.

Пример для рисунка:

1. Робот стартует под горизонтальной стеной.
2. Движется вправо, пока не упрется в вертикальную стену.
3. Закрашивает все клетки под горизонтальной стеной, пока не дойдет до вертикальной стены.
4. Затем движется вниз, закрашивая все клетки правее вертикальной стены, пока не достигнет нижней границы.
5. Проход в горизонтальной стене и вертикальной стене должны быть пропущены.

Ключевые команды (псевдокод):

ЕСЛИ НЕ ПРЕПЯТСТВИЕ_СПРАВА И НЕ_УПЕРЛИСЬ_В_СТЕНУ: ДВИГАТЬСЯ_ВПРАВО
ЕСЛИ КЛЕТКА_ДОЛЖНА_БЫТЬ_ЗАРАШЕНА: ЗАРАШИВАТЬ
ЕСЛИ ПРЕПЯТСТВИЕ_ВНИЗУ: ОБОЙТИ_ИЛИ_ОСТАНОВИТЬСЯ
ДВИГАТЬСЯ_ВНИЗ

Важно: Алгоритм должен быть рекурсивным или использовать стек для обработки сложных лабиринтов с проходами.