算法來尋找和填補網格

封閉形狀所以說我們有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 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

實施洪水填充算法是容易的，但我不能想出一個辦法來（編程）填寫在網格中所有封閉的任意形狀。是否有任何類型的算法或搜索可以用於此目的？

來源

2017-01-19 office_boy

洪水填充算法有什麼問題？這是簡單的結束與複雜性O（N）有效。

首先掃描零值的邊緣並填充標記值爲3的空白區域。然後穿過內部的地方。如果您發現零細胞，由此細胞洪水填充值2

（也許你正在尋找類似connected-component labeling algorithm。它的目的是通過標記標記獨特值的每個連接區域）

來源

2017-01-19 17:05:20 MBo

你可以先找到零的邊界路徑：

在邊界上取任意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 ... 
}

來源

2017-01-19 17:10:22

算法來尋找和填補網格

回答

相關問題