Поиск всех похожих соседей в группе - необходима рекурсивная функция

Question

У меня есть проблема, когда я уверен, что, вероятно, уже существует множество эффективных решений. Для упрощения предположим, что ячейки сетки имеют ширину ячеек двух типов: ячейки "X" и ячейки "o".

 5 +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|X|X|o|o|o|o|o|X
 4 +-+-+-+-+-+-+-+-+-+-+-+
   |o|X|o|o|X|o|o|o|o|o|X
 3 +-+-+-+-+-+-+-+-+-+-+-+
   |o|X|X|X|X|o|o|X|o|o|X
 2 +-+-+-+-+-+-+-+-+-+-+-+
   |X|o|o|X|X|X|X|X|X|o|X
 1 +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|o|X|X|X|o|o|o|X 
   +-+-+-+-+-+-+-+-+-+-+-+
 0   1 2 3 4 5 6 7 8

Теперь выбирается одна из ячеек "Х".

   +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|X|X|o|o|o|o|o|X
   +-+-+-+-+-+-+-+-+-+-+-+
   |o|X|o|o|X|o|o|o|o|o|X
   +-+-+-+-\-/-+-+-+-+-+-+
   |o|X|X|X<*>o|o|X|o|o|X
   +-+-+-+-/-\-+-+-+-+-+-+
   |X|o|o|X|X|X|X|X|X|o|X
   +-+-+-+-+-+-+-+-+-+-+-+
   |X|X|o|o|X|X|X|o|o|o|X 
   +-+-+-+-+-+-+-+-+-+-+-+

Что мне нужно выяснить, так это все соседние ячейки "Х" покрытой области "Х", частью которой является выбранная ячейка. Ячейки "X", которые не связаны напрямую и не отделены ячейкой "o" от группы, исключаются. Смотрите иллюстрацию ниже.

   +.+.+-+.+.+-+-+-+-+-+-+
   :   :o:   :o|o|o|o|o|X
   +.+ +-+.+ +-+-+-+-+-+-+
   |o: :o|o: :o|o|o|o|o|X
   +-+ +.+.+ +-+-+.+-+-+-+
   |o:       :o|o: :o|o|X
   +-+.+.     .+.+ +.+-+-+
   |X|o|o:           |o|X
   +-+-+-+.+     +.+.+-+-+
   |X|X|o|o:     :o|o|o|X 
   +-+-+-+-+.+.+.+-+-+-+-+

В основном это простая функция "Заполнить", где мне нужно найти границы этой области для заполнения. Я уверен, что существует даже определенное название для такого рода вещей. Скажите мне, что также будет оценено:)

Answer 1

Название алгоритма, который вам нужен - Flood Fill. У меня есть короткий пример кода (в F#), используемый для клона Pacman.