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

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

Задача: Закрасить определенные клетки, избегая стены и пропуская проходы.

Условия закрашивания:

• Ниже первого отрезка стены (горизонтальный, вправо).
• Левее второго отрезка стены (вертикальный, вниз).
• Левее четвертого отрезка стены (вертикальный, вниз).
• Ниже пятого отрезка стены (горизонтальный, вправо).
• Клетка X (если она попадает под условия).

  Начальное положение робота: самая левая клетка непосредственно под верхней горизонтальной стеной.

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

  1. Разведка и картографирование:
  • Робот должен сначала исследовать поле, чтобы определить расположение стены (все 5 отрезков) и границы закрашиваемой области.
  • Он может двигаться по полю, отмечая пройденные клетки и распознавая стены.
  2. Определение целевых областей:
  • Область 1: Ниже первого отрезка. Это область под начальным горизонтальным отрезком стены.
  • Область 2: Левее второго отрезка. Это область слева от первого вертикального отрезка.
  • Область 3: Левее четвертого отрезка. Это область слева от второго вертикального отрезка.
  • Область 4: Ниже пятого отрезка. Это область под вторым горизонтальным отрезком.
  • Клетка X: Должна быть проверена на соответствие любому из вышеуказанных условий.
  3. Алгоритм закрашивания:
  • Фаза 1 (Закрашивание под первым отрезком):
  • Находясь под первым горизонтальным отрезком, двигаться вправо, закрашивая каждую клетку, пока не будет достигнута граница этой области (например, другой отрезок стены или край поля).
  • Фаза 2 (Закрашивание левее второго отрезка):
  • Переместиться к началу второго отрезка.
  • Двигаться влево, закрашивая каждую клетку, пока не будет достигнута граница.
  • Фаза 3 (Закрашивание левее четвертого отрезка):
  • Переместиться к началу четвертого отрезка.
  • Двигаться влево, закрашивая каждую клетку, пока не будет достигнута граница.
  • Фаза 4 (Закрашивание ниже пятого отрезка):
  • Переместиться к началу пятого отрезка.
  • Двигаться вниз, закрашивая каждую клетку, пока не будет достигнута граница.
  • Фаза 5 (Клетка X):
  • Если клетка X была не закрашена на предыдущих этапах, но подпадает под одно из условий, закрасить ее.
  4. Безопасность и завершение:
  • Робот должен всегда проверять наличие стены перед движением.
  • Использовать алгоритмы обхода препятствий (например, "обход стены справа"), если необходимо пройти через сложные участки или обойти проходы.
  • Алгоритм должен завершиться, когда все целевые клетки будут закрашены, и робот не сможет найти новых клеток для закрашивания.

  Пример на основе рисунка:

  1. Робот стартует под верхней горизонтальной линией.
  2. Он закрашивает клетки под этой линией, пока не дойдет до вертикальной стены (второй отрезок).
  3. Затем он перемещается к началу второго отрезка (вертикального).
  4. Закрашивает клетки слева от этого вертикального отрезка.
  5. Перемещается к началу четвертого отрезка (вертикального).
  6. Закрашивает клетки слева от этого вертикального отрезка.
  7. Перемещается к началу пятого отрезка (горизонтального).
  8. Закрашивает клетки под этим горизонтальным отрезком.
  9. Клетка 'X' (если она находится в области, удовлетворяющей условиям) будет закрашена.

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

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