如何在2D矩阵中找到空洞？

Question

我知道标题看起来有点模棱两可，因此我附上了一张图片，这将有助于清楚地理解这个问题。我需要找出白色区域内的洞。一个洞被定义为白色区域内一个或多个值为'0‘的单元格，我的意思是它必须被值为'1’的单元格完全包围(例如，我们在这里可以看到三个洞被标记为1，2和3)。我想出了一个相当幼稚的解决方案: 1.在整个矩阵中搜索值为'0‘的单元格。2.当遇到这样的单元格(黑色单元格)时，运行DFS(Flood-Fill)，并检查我们是否可以接触到主要矩形区域的边界3.如果我们在DFS过程中可以接触到边界，则它不是一个洞，如果我们不能到达边界，那么它将被认为是一个洞

现在，这个解决方案起作用了，但我想知道是否有其他有效/快速的解决方案来解决这个问题。

请让我知道你的想法。谢谢。

​

​

Answer 1

用floodfill填充，你已经有了：沿着矩阵的边界运行并填充它，即将全0(黑色)改为2(黑色填充)，将1改为3(白色填充)；忽略来自早期填充的2和3。

例如，你的矩阵从左上角开始，用区域11填充黑色区域，然后向右移动，找到一个刚刚填充的黑色单元格。再次向右移动，找到一个白色区域，非常大(实际上是矩阵中的所有白色区域)。把它填满。然后你再次向右移动，另一个新的黑色区域沿着整个上边界和右边界运行。移动一下，您现在可以找到两个先前填充的白色单元格并跳过它们。最后，你会发现沿着底部边框的黑色区域。

计算你找到和设置的颜色的数量可能已经提供了矩阵中是否有空洞的信息。

否则，或者要找到它们所在的位置，请扫描矩阵:您找到的所有颜色仍为0的区域都是黑色中的空洞。你也可能在白纸上有洞。

另一种方法，类似于“ flood”

在第一个矩阵的边界上运行。在你找到"0“的地方，你设置为"2”。在你找到"1“的地方，你设置为"3”。

现在绕过新的内部边框(那些接触到您刚刚扫描的边框的单元格)。接触2的0个单元格变成2，接触3的1个单元格变成3。

您必须扫描两次，一次顺时针，一次逆时针，检查当前单元格的“向外”和“在前”。这是因为你可能会找到类似这样的东西：

22222222222333333
2AB11111111C
31

单元格A实际上是1。你检查它的邻居，你会发现1 (但检查它是没有用的，因为你还没有处理它，所以你不能知道它是1还是应该是3--顺便说一句，就是这种情况)，2和2。2不能改变1，所以单元格A仍然是1。单元格B也是1，依此类推。当您到达单元格C时，您发现它是一个1，并且有一个3邻居，因此它切换为3…但是从A到C的所有单元格现在都应该切换。

最简单但不是最有效的方法是顺时针扫描单元格，这会给出错误的答案(顺便说一句，C和D是1)

22222222222333333
211111111DC333333
33

然后再逆时针扫描一次。现在，当您到达单元格C时，它有一个3邻居，并切换到3。接下来，您检查单元格D，它以前的邻居是C，现在是3，所以D再次切换到3。最后你会得到正确的答案。

22222222222333333
23333333333333333
33

对于每个单元，你检查了两个顺时针方向的邻居，一个是逆时针方向。此外，其中一个邻居实际上是您刚才检查的单元格，因此您可以将其保存在一个就绪变量中，从而节省一次矩阵访问。

如果你发现你扫描了整个边框而没有切换一个单元格，你可以停止这个过程。检查这个将花费你2次(W*H)操作，所以只有在有很多洞的情况下它才是真正值得的。

在最多W*H*2个步骤中，您应该已经完成了。

您可能还想检查渗流算法，并尝试调整该算法。

Answer 2

创建某种类型的"LinkedCells“类，用于存储相互链接的单元格。然后按从左到右自上而下的顺序逐个检查单元格，对每个单元格进行以下检查:如果相邻单元格为黑色-将此单元格添加到该单元格的组中。否则，您应该为此单元格创建新组。您应该只检查顶部和左侧邻居。

更新：对不起，我忘记了合并分组:如果两个相邻的单元都是黑色的，并且来自不同的分组-你应该合并成一个分组。

如果您的"LinkedCells“类连接到边缘，那么它应该有一个标志。默认情况下为false，如果将边缘单元添加到此组中，则可以更改为true。在合并两个组的情况下，您应该将新标志设置为先前标志的||。最后，您将拥有一组组，并且每个具有错误连接标志的组都将是“空洞”。

这个算法将是O(x*y)。

Answer 3

您可以将栅格表示为一个图形，其中各个单元作为顶点，边出现在相邻顶点之间。然后，您可以使用广度优先搜索或深度优先搜索从每个单元格的侧面开始。由于您只会发现连接到侧面的组件，因此尚未访问的黑色单元格是孔。您可以再次使用搜索算法将孔划分为不同的组件。

编辑:最坏情况下的复杂度必须与单元格的数量成线性关系，否则，给算法一些输入，检查算法没有检查到的单元格(因为你是次线性的，会有大的未访问的点)，并在那里放一个洞。现在你已经得到了一个输入，对于这个输入，算法找不到其中一个洞。