如何在二维矩阵中找到洞? [英] How can I find hole in a 2D matrix?

问题描述

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

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

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

解决方案

使用您已有的洪水填充:沿着矩阵的边界运行并进行洪水填充，即，将所有零(黑色)更改为 2(填充黑色)，将 1 更改为 3(填充白色)；忽略来自早期洪水填充的 2 和 3.

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

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

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

另一种方法，类似于拦洪填埋"

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

现在绕过新的内边界(那些接触到您刚刚扫描的边界的单元格).零个细胞接触 2 变成 2，1 个细胞接触 3 变成 3.

您必须扫描两次，一次顺时针，一次逆时针，检查当前单元格向外"和之前"的单元格.那是因为你可能会发现这样的东西:

222222222223333332AB11111111C31

Cell A 实际上是 1.你检查它的邻居，你会发现 1(但是检查 那个 没用，因为你还没有处理它，所以你不能知道它是否是 1或者应该是 3 - 顺便说一下)，2 和 2.A 2 不能改变 1，所以单元格 A 保持 1.同样的单元格 B 也是 1，依此类推.当您到达单元格 C 时，您发现它是 1，并且有一个 3 邻居，因此它切换到 3...但是从 A 到 C 的所有单元格现在应该切换.>

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

22222222222333333211111111DC33333333

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

222222222223333332333333333333333333

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

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

最多 W*H*2 步，你应该完成.

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

I know the title seems kind of ambiguous and for this reason I've attached an image which will be helpful to understand the problem clearly. I need to find holes inside the white region. A hole is defined as one or many cells with value '0' inside the white region I mean it'll have to be fully enclosed by cell's with value '1' (e.g. here we can see three holes marked as 1, 2 and 3). I've come up with a pretty naive solution: 1. Search the whole matrix for cells with value '0' 2. Run a DFS(Flood-Fill) when such a cell (black one) is encountered and check whether we can touch the boundary of the main rectangular region 3. If we can touch boundary during DFS then it's not a hole and if we can't reach boundary then it'll be considered as a hole

Now, this solution works but I was wondering if there's any other efficient/fast solution for this problem.

Please let me know your thoughts. Thanks.

解决方案

With floodfill, which you already have: run along the BORDER of your matrix and floodfill it, i.e., change all zeroes (black) to 2 (filled black) and ones to 3 (filled white); ignore 2 and 3's that come from an earlier floodfill.

For example with your matrix, you start from the upper left, and floodfill black a zone with area 11. Then you move right, and find a black cell that you just filled. Move right again and find a white area, very large (actually all the white in your matrix). Floodfill it. Then you move right again, another fresh black area that runs along the whole upper and right borders. Moving around, you now find two white cells that you filled earlier and skip them. And finally you find the black area along the bottom border.

Counting the number of colours you found and set might already supply the information on whethere there are holes in the matrix.

Otherwise, or to find where they are, scan the matrix: all areas you find that are still of color 0 are holes in the black. You might also have holes in the white.

Another method, sort of "arrested flood fill"

Run all around the border of the first matrix. Where you find "0", you set to "2". Where you find "1", you set to "3".

Now run around the new inner border (those cells that touch the border you have just scanned). Zero cells touching 2's become 2, 1 cells touching 3 become 3.

You will have to scan twice, once clockwise, once counterclockwise, checking the cells "outwards" and "before" the current cell. That is because you might find something like this:

22222222222333333
2AB11111111C
31

Cell A is actually 1. You examine its neighbours and you find 1 (but it's useless to check that since you haven't processed it yet, so you can't know if it's a 1 or should be a 3 - which is the case, by the way), 2 and 2. A 2 can't change a 1, so cell A remains 1. The same goes with cell B which is again a 1, and so on. When you arrive at cell C, you discover that it is a 1, and has a 3 neighbour, so it toggles to 3... but all the cells from A to C should now toggle.

The simplest, albeit not most efficient, way to deal with this is to scan the cells clockwise, which gives you the wrong answer (C and D are 1's, by the way)

22222222222333333
211111111DC333333
33

and then scan them again counterclockwise. Now when you arrive to cell C, it has a 3-neighbour and toggles to 3. Next you inspect cell D, whose previous-neighbour is C, which is now 3, so D toggles to 3 again. In the end you get the correct answer

22222222222333333
23333333333333333
33

and for each cell you examined two neighbours going clockwise, one going counterclockwise. Moreover, one of the neighbours is actually the cell you checked just before, so you can keep it in a ready variable and save one matrix access.

If you find that you scanned a whole border without even once toggling a single cell, you can halt the procedure. Checking this will cost you 2(W*H) operations, so it is only really worthwhile if there are lots of holes.

In at most W*H*2 steps, you should be done.

You might also want to check the Percolation Algorithm and try to adapt that one.

这篇关于如何在二维矩阵中找到洞?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！