algorithm - 如何在二维矩阵中找到孔？

Question

我知道标题似乎有点模棱两可，因此我附上了一张有助于清楚地理解问题的图片。我需要在白色区域内找到洞。孔被定义为白色区域内一个或多个值为“0”的单元格，我的意思是它必须被值为“1”的单元格完全包围(例如，这里我们可以看到三个标记为 1、2 和 3 的孔).我想出了一个非常天真的解决方案:1. 在整个矩阵中搜索值为“0”的单元格2.遇到这样的单元格(黑色单元格)时运行DFS(Flood-Fill)并检查我们是否可以触及主要矩形区域的边界3. DFS时如果能碰到边界就不是洞，不能碰到边界就认为是洞

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

请告诉我您的想法。谢谢。

Answer 1

使用您已经拥有的 floodfill:沿着矩阵的 BORDER 运行并对其进行 floodfill，即将所有零(黑色)更改为 2(填充黑色)并将一个更改为 3(填充白色)；忽略来自早期 floodfill 的 2 和 3。

例如，对于您的矩阵，您从左上角开始，用黑色填充区域为 11 的区域。然后向右移动，找到您刚刚填充的黑色单元格。再次向右移动，找到一个非常大的白色区域(实际上矩阵中的所有白色区域)。淹没它。然后你再次向右移动，另一个新的黑色区域沿着整个上边界和右边界延伸。四处走动，您现在发现两个您之前填充的白色单元格并跳过它们。最后，您会在底部边框找到黑色区域。

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

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

另一种方法，类似于“拦洪填充”

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

现在绕着新的内部边框(那些接触您刚刚扫描的边框的单元格)运行。接触 2 的零单元格变为 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 的所有单元格现在都应该切换。。 p>

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

22222222222333333
211111111DC333333
33

然后逆时针再次扫描它们。现在，当您到达单元格 C 时，它有一个 3-neighbor 并切换到 3。接下来您检查单元格 D，其先前的邻居是 C，现在是 3，因此 D 再次切换到 3。最终得到正确答案

22222222222333333
23333333333333333
33

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

如果您发现您扫描了整个边框而甚至一次 都不切换单个单元格，您可以停止该过程。检查这将花费您 2(W*H) 次操作，因此只有当存在 很多 个漏洞时才真正值得。

最多 W*H*2 步，您应该完成。

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