Окруженный алгоритм области

Question

Проблемы «Окруженный Регион» гласит:.

«Учитывая 2D доску, содержащая„X“и„O“, охватить все регионы, окруженные„X“ Области захватывается листать все" О в «Х в этом окруженном регионе».

Я смущен, что касается этой проблемы. Я не понимаю, что диктует, когда в регионе «окружен», основанный на всех примерах, найденных в Интернете (которые, случается, со всеми похожими примерами).

Приведенный пример.

input        output 

X X X X       X X X X 
X O O X       X X X X 
X X O X       X X X X 
X O X X       X O X X 

Обе группы выглядят O в окружении крестиков мне. Является ли правило, что все четыре стороны должны быть окружены X? и так как внизу O не имеет X ниже, это не 'capt'?

Что произойдет, если это вход? ничего снято?

X X X X        
X O O O       
X X O X       
X O X X        

Answer 1

Согласно определению, если «O» клетка окружена клетками «X», т.е. вверх/вниз/влево/вправо клетки «X». Первая мысль может быть для каждой ячейки «O», добавить ее в массив, проверить ее вверх/вниз/влево/вправо, и если это еще одна ячейка «O», продолжайте, пока она не ударит по всем ячейкам «X» или граница хитов. В первом случае ячейки в массиве могут быть перевернуты до'X '; в то время как в последнем случае ячейки в массиве не могут быть перевернуты.

Answer 2

Да, точно.
Это окружение и захват на самом деле, как игра (GO). Края не могут быть захвачены, вот и все. Если вы поместите свои точки в край, они будут вашими до конца игры. Также, окружающие средства, if O's are surrounded by X's, then X's will form a cycle around O's. And whenever such a cycle completes, all the inside O's will be flipped to X's and vice-versa.
определение цикла:
Цикл иксы или Выходов любая связная область, где вы начинаете из клетки и вернуться к нему, не повторяя (пересматривают) клетки, и каждый шаг, который вы можете взять chess piece king's движение для завершения пути.
Итак, в вашем примере ввода путь:
(1,0) -> (0,1) -> (0,2) -> (1,3) -> (2,3) -> (3,2) -> (2,1) -> (1,0) образует цикл.