Заливка области (Flood Fill)

Классический алгоритм заливки замкнутой области -- тот самый, что используется в инструменте "Заливка" графических редакторов. Робот рекурсивно обходит все доступные клетки и закрашивает их.

Идея алгоритма

Если текущая клетка уже закрашена -- выходим (базовый случай рекурсии)
Закрашиваем текущую клетку
Для каждого из четырёх направлений (вверх, вниз, влево, вправо):
- Если в этом направлении нет стены, шагаем туда
- Рекурсивно запускаем заливку из новой клетки
- Возвращаемся обратно
В итоге вся связная область, ограниченная стенами, будет закрашена

Разбор

Главный алгоритм

использовать Робот

алг заливка
нач
  залей
кон

Главный алгоритм заливка просто вызывает рекурсивный алгоритм залей. Такое разделение делает код чище: точка входа отделена от рекурсивной логики.

Базовый случай рекурсии

алг залей
нач
  если клетка закрашена
    то
      выход
  все

клетка закрашена -- проверяет, закрашена ли текущая клетка
Если клетка уже закрашена, значит мы здесь уже были -- выход прерывает выполнение алгоритма
Без этой проверки Робот зациклится, бесконечно возвращаясь в уже посещённые клетки

Закрашивание и рекурсивный обход соседей

  закрасить

  если сверху свободно
    то
      вверх
      залей
      вниз
  все

  если снизу свободно
    то
      вниз
      залей
      вверх
  все

  если слева свободно
    то
      влево
      залей
      вправо
  все

  если справа свободно
    то
      вправо
      залей
      влево
  все
кон

Для каждого направления выполняется одна и та же тройка действий:

Шаг -- Робот перемещается в соседнюю клетку (например, вверх)
Рекурсия -- вызывается залей, который закрасит всё, что можно достать из новой клетки
Возврат -- Робот возвращается обратно противоположной командой (например, вниз)

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

Закрашенные клетки играют роль меток посещённых вершин, как в обходе графа в ширину или глубину. Здесь используется обход в глубину (DFS).

Полная программа

использовать Робот

алг заливка
нач
  залей
кон

алг залей
нач
  если клетка закрашена
    то
      выход
  все

  закрасить

  если сверху свободно
    то
      вверх
      залей
      вниз
  все

  если снизу свободно
    то
      вниз
      залей
      вверх
  все

  если слева свободно
    то
      влево
      залей
      вправо
  все

  если справа свободно
    то
      вправо
      залей
      влево
  все
кон

▶ Запустить пример