Алгоритм поиска и заполнить приложенные формы на сетке

Question

Так что у нас есть пустая сетка 0s:

0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 

И вы можете рисовать фигуры на нем. 1 представляет собой заполненную ячейку.

1 1 1 1 0 0 0 0 
1 0 0 1 0 0 0 0 
1 0 0 1 0 0 0 0 
1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 1 0 0 1 1 1 
1 0 0 1 0 1 0 0 
0 1 1 0 0 1 0 0 

Рассмотрена форма замкнутого, если четыре-направленный алгоритм наводнения заполнения не будет течь и заполнять любые клетки вне формы. Форма не может использовать границу сетки как одну из ее сторон. Так что, если мы заполнили все замкнутые формы в этой сетке с 2s, мы имеем:

1 1 1 1 0 0 0 0 
1 2 2 1 0 0 0 0 
1 2 2 1 0 0 0 0 
1 1 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 1 0 0 1 1 1 
1 2 2 1 0 1 0 0 
0 1 1 0 0 1 0 0 

Реализация Flood-заливку алгоритм прост, но я не могу понять, путь к (программно) заполнить во всех замкнутых произвольных фигурах в сетке. Существуют ли какие-либо типы алгоритмов или поисков, которые я мог бы использовать для этого?

Answer 1

Что случилось с алгоритмом наводнения? Это простой конец, эффективный со сложностью O (N).

Сперва сканирование краев для нулевых значений и областей пустых пустот с отметкой 3. Затем пройдите по внутреннему месту. Если вы обнаружили нулевую ячейку, наводнение заполнения из этой ячейки со значением 2.

(Возможно, вы ищете что-то вроде connected-component labeling algorithm. Он предназначен, чтобы отметить каждую подключенную область уникального значения метки)

Answer 2

Вы можете сначала найти нулевые, которые имеют путь к границе:

Возьмите произвольную 0 ячейку на границе, отметьте ее как -1, сделайте это для всех своих соседних ячеек рекурсивно (соседи соседей и т. д. все установлены в -1). Как только ни одна из граничных ячеек не равна нулю, поверните все нулевые ячейки на 2. Это означает, что они окружены только 1. В конце концов все -1 на 0. Это O (n), где n - количество ячеек в сетке.

Вот (ленивый) псевдо-код, предполагая, что мы имеем n_1xn_2 сетки:

function fill() 
{ 
for int i=1..n_1 
{ 
    recursivecolor(i,1); 
    recursivecolor(i,n_2); 
} 

for int j=1..n_2 
{ 
    recursivecolor(1,j); 
    recursivecolor(n_1,j); 
} 

for i=1..n_1 
    for j=1 .. n_2 
    if (a[i][j] == 0) 
     a[i][j] = 2; 

for i=1..n_1 
    for j=1 .. n_2 
    if (a[i][j] == -1) 
     a[i][j] = 0; 
} 


function recursivecolor(i,j) 
{ 
    if (a[i][j]!=0) return; 

    a[i][j] = -1; 
    if (a[i-1][j] == 0) 
    { 
     a[i-1][j] = -1; 
     recursivecolor(i-1,j); 
    } 
    // do this for all neighbours of i,j cell 
    // it also needs check for boundaries, e.g. i-1 should not be zero ... 
}