알고리즘 찾아 그래서 우리는 0의 빈 그리드가 있다고 그리드

Question

에 둘러싸인 모양을 채우기 위해 :

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 

4 방향 플러드 채우기 알고리즘이 누출되어 모양 외부의 셀을 채우지 않으면 모양이 닫힌 것으로 간주됩니다. 도형은 격자의 경계를 그 변의 하나로서 사용할 수 없습니다. 우리가 2 초이 그리드의 닫힌 형태의 모든 채워진다면, 우리는 할 것이다 :

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 

알고리즘은 쉽게 홍수 채우기를 구현,하지만 난 (프로그래밍 방식)을 작성하는 방법을 알아낼 수 없습니다 그리드의 모든 밀폐 된 임의의 도형에서. 이 알고리즘에 사용할 수있는 알고리즘이나 검색 유형이 있습니까?

Answer 1

홍수 채우기 알고리즘에는 어떤 문제가 있습니까? 복잡성이 O (N) 인 단순한 최종 효과적입니다.

처음에는 0 값의 가장자리를 스캔하고 빈 값을 3으로 채 웁니다. 그런 다음 내부 위치를 통과합니다. 당신이 제로 세포를 발견하면, 값이 셀에서 홍수 채우기 2.

(아마도 당신이 connected-component labeling algorithm 뭔가를 찾고 있습니다. 고유의 마크 값에 의해 연결된 모든 영역을 표시하기위한 것입니다)

Answer 2

것은 먼저 찾을 수 있습니다 경계에 대한 경로를 가진 0이됩니다.

경계에서 임의의 0 셀을 가져 와서 -1로 표시하고 이웃 셀의 모든 인접 셀에 대해 재귀 적으로 반복합니다 (이웃의 이웃과 모든 셀을 모두 -1로 설정). 일단 경계 셀이 0이 아니면, 모든 제로 셀을 2로 바꿉니다. 이것은 1로 둘러싸인다는 것을 의미합니다. 결국 모든 -1을 0으로 바꿉니다. 이것은 O (n)입니다. n은 그리드의 셀 수입니다.

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 ... 
} 

: 여기

우리가 n_1xn_2 그리드를 가정하는 (게으른) 의사 코드