算法来寻找和填补网格

封闭形状所以说我们有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

算法来寻找和填补网格

回答

相关问题