如何在二维矩阵中找到洞?

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

我知道标题似乎有点模棱两可，因此我附上了一张图片，这将有助于清楚地理解问题。我需要找到白色区域内的洞。一个洞被定义为一个或多个细胞值“0”在白色区域我意味着它会有被细胞的全封闭值“1”(例如,在这里我们可以看到三个孔标记为1,2,3)。我想出一个很天真的解决方案:1。在整个矩阵中搜索值为'0' 2的单元格。当遇到这样一个单元(黑色单元)时，运行DFS(注水)，并检查我们是否可以触及主矩形区域3的边界。如果我们可以在DFS中接触到边界那么它就不是一个洞如果我们不能接触到边界那么它就会被认为是一个洞

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.

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

5 个解决方案

#1

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.

有了洪泛填充，你已经有了:沿着你的矩阵的边界运行洪泛填充，也就是。，将所有0(黑色)更改为2(黑色填充)，1更改为3(白色填充);忽略2和3来自早期的洪水填充。

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.

例如，你的矩阵，你从左上角开始，洪水填充黑色区域与第11区。然后你右移，找到一个你刚刚填充的黑色细胞。再向右移动，找到一个非常大的白色区域(实际上是你矩阵中的所有白色区域)。Floodfill它。然后你再向右移动，另一个新的黑色区域沿着整个上、右边界延伸。四处移动，您现在找到了两个先前填充的白细胞，并跳过它们。最后你会发现沿着底部边界的黑色区域。

Then 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.

然后扫描矩阵:你发现的所有仍然是颜色0的区域都是黑色的洞。白色部分也可能有洞。

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".

绕着第一个矩阵的边界跑。在找到“0”的地方，设置为“2”。在找到“1”的地方，设置为“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.

现在绕着新的内边界(那些接触你刚刚扫描的边界的细胞)运行。0个接触2的细胞变成2,1个接触3的细胞变成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.

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

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)

最简单的，虽然不是最有效的方法，是顺时针扫描细胞，这会给你错误的答案(顺便说一下，C和D是1)

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

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

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.

如果您发现您扫描了整个边框，甚至一次都没有移动一个单元格，您可以停止这个过程。检查这将花费你2(W*H)操作，所以只有当有很多洞的时候才真正值得。

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

在最多2个步骤中，你应该完成。

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

您可能还需要检查渗透算法并尝试调整它。

#2

Make some sort of a "LinkedCells" class that will store cells that are linked with each other. Then check cells on-by-one in a from-left-to-right-from-top-to-bottom order, making the following check for each cell: if it's neighbouring cell is black - add this cell to that cell's group. Else you should create new group for this cell. You should only check for top and left neighbour.
UPD: Sorry, I forgot about merging groups: if both neighbouring cells are black and are from different groups - you should merege tha groups in one.

创建某种“连接单元”类，它将存储相互连接的单元格。然后按从左到右从上到下的顺序逐个检查单元格，对每个单元格进行以下检查:如果相邻的单元格是黑色的，将该单元格添加到该单元格的组中。否则，您应该为这个单元格创建新的组。你应该只检查顶部和左边的邻居。不好意思，我忘记合并组了:如果两个相邻的细胞都是黑色的，并且来自不同的组——你应该把所有的组合并在一起。

Your "LinkedCells" class should have a flag if it is connected to the edge. It is false by default and can be changed to true if you add edge cell to this group. In case of merging two groups you should set new flag as a || of previous flags. In the end you will have a set of groups and each group having false connection flag will be "hole".

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

This algorithm will be O(x*y).

这个算法是O(x*y)

#3

You can represent the grid as a graph with individual cells as vertexes and edges occurring between adjacent vertexes. Then you can use Breadth First Search or Depth First Search to start at each of the cells, on the sides. As you will only find the components connected to the sides, the black cells which have not been visited are the holes. You can use the search algorithm again to divide the holes into distinct components.

您可以将网格表示为一个图，其中单个单元格表示为顶点，而相邻顶点之间的边表示为边。然后你可以使用广度优先搜索或者深度优先搜索从每一个单元格开始，在两边。因为你只会发现连接到两边的元件，所以没有被探测到的黑洞就是黑洞。您可以再次使用搜索算法将漏洞划分为不同的组件。

EDIT: Worst case complexity must be linear to the number of cells, otherwise, give some input to the algorithm, check which cells (as you're sublinear, there will be big unvisited spots) the algorithm hasn't looked into and put a hole in there. Now you've got an input for which the algorithm doesn't find one of the holes.

编辑:最坏的情况是，复杂度必须与单元数成线性关系，否则，给算法一些输入，检查哪些单元数(因为你是次盲，所以会有大的未访问点)，算法没有检查过，并在其中留下一个洞。现在你有了一个输入，算法没有找到一个洞。

#4

Your algorithm is globally Ok. It's just a matter of optimizing it by merging the flood fill exploration with the cell scanning. This will just minimize tests.

你的算法是全局的。这只是通过将洪水填充探索与细胞扫描相结合来优化它的问题。这将使测试最小化。

The general idea is to perform the flood fill exploration line by line while scanning the table. So you'll have multiple parallel flood fill that you have to keep track of.

一般的思路是在扫描表格的同时，逐行进行注水勘探。你需要跟踪多个平行的洪水填充。

The table is then processed row by row from top to bottom, and each row processed from right to left. The order is arbitrary, could be reverse if you prefer.

然后从上到下逐行处理表，从右到左处理每一行。顺序是任意的，如果你喜欢可以反过来。

Let segments identify a sequence of consecutive cells with value 0 in a row. You only need the index of the first and last cell with value 0 to define a segment. As you may guess a segment is also a flood fill in progress. So we'll add an identification number to the segments to distinguish between the different flood fills.

让分段识别一行中值为0的连续单元格序列。只需要第一个和最后一个单元格的索引(值为0)就可以定义一个段。正如你所猜测的那样，一个片段也是一个洪水填充的过程。因此，我们将在片段中添加一个识别号，以区分不同的洪水填充。

The nice thing of this algorithm is that you only need to keep track of segments and their identification number in row i and i-1. So that when you process row i, you have the list of segments found in the row i-1 and their associated identification number.

这个算法的优点是你只需要跟踪第i行和第i-1行中的段及其识别号。所以当你处理第i行时，你有在第i-1行中找到的段的列表以及它们相关的识别号。

You then have to process segment connection in row i and row i-1. I'll explain below how this can be made efficient.

然后，您必须处理第i行和第i-1行中的段连接。下面我将解释如何提高效率。

For now you have to consider three cases:

现在你必须考虑三种情况:

1. found a segment in row i not connected to a segment in row i-1. Assign it a new hole identification (incremented integer). If it's connected to the border of the table, make this number negative.

   找到第i行中未连接到第i-1行的段的段。给它分配一个新的孔标识(递增整数)。如果它连接到表格的边框，让这个数字为负数。

2. found a segment in row i-1 not connected to a segment in row i-1. You found the lowest segment of a hole. If it has a negative identification number it is connected to the border and you can ignore it. Otherwise, congratulation, you found a hole.

   发现第i-1行中没有连接到第i-1行中的段的段。你找到了一个洞的最低部分。如果它的识别码是负数，那么它就与边界相连，你可以忽略它。否则，恭喜，你发现了一个洞。

3. found a segment in row i connected to one or more segments in row i-1. Set the identification number of all these connected segments to the smallest identification number. See the following possible use case.

   发现第i行中的一个段连接到第i行中的一个或多个段。将所有这些连接段的识别号设置为最小的识别号。请参见以下可能的用例。

row i-1:   2  333 444 111
row i  :  ****  *** ***

The segments in row i should all get the value 1 identifying the same flood fill.

行i的分段都应该得到值1，以确定相同的洪水填充。

Matching segments in rows i and row i-1 can be done efficiently by keeping them in order from left to right and comparing segments indexes.

匹配第i行和第i-1行中的段可以通过保持它们从左到右的顺序以及比较段索引来有效地完成。

Process segments by lowest start index first. Then check if it's connected to the segment with lowest start index of the other row. If no, process case 1 or 2. Otherwise continue identifying connected segments, keeping track of the smallest identification number. When no more connected segments is found, set the identification number of all connected segments found in row i to the smallest identification value.

流程段首先按最低开始索引。然后检查它是否连接到另一行的最低起始索引段。如果没有，处理案例1或2。否则继续识别连接段，跟踪最小的识别号。当发现没有连接的线段时，将第i行中发现的所有连接段的标识号设置为最小的标识值。

Index comparison for connectivity test can by optimized by storing (first-1,last) as segment definition since segments may be connected by their corners. You then can directly compare indexes bare value and detect overlapping segments.

连接测试的索引比较可以通过存储(前1，最后)作为段定义进行优化，因为段可以通过它们的角进行连接。然后可以直接比较索引裸值，并检测重叠部分。

The rule to pick the smallest identification number ensures that you automatically get the negative number for connected segments and at least one connected to the border. It propagates to other segments and flood fills.

选择最小识别号的规则确保您自动获得连接段的负数和至少一个连接到边界的负数。它会传播到其他区段和洪水填充物。

This is a nice exercise to program. You didn't specify the exact output you need. So this is also left as exercise.

这是一个很好的练习。您没有指定所需的确切输出。这也是我们的练习。

#5

The brute force algorithm as described here is as follow.

这里描述的蛮力算法如下。

We now assume we can write in cells a value different from 0 or 1.

我们现在假设我们可以在单元格中写入不同于0或1的值。

You need a flood fill functions receiving the coordinates of a cell to start from and an integer value to write into all connected cells holding the value 0.

您需要一个接收要开始的单元格坐标的泛流填充函数，以及一个要写入所有连接的单元格中的值为0的整数值。

Since you need to only consider holes (cells with value 0 surrounded by cells with value 1), you have to use two pass.

由于您只需要考虑空穴(值为0的单元格被值为1的单元格包围)，您必须使用两次遍历。

A first pass visit only cells touching the border. For every cell containing the value 0, you do a flood fill with the value -1. This tells you that this cell has a value different of 1 and has a connection to the border. After this scan, all cells with a value 0 belong to one or more holes.

第一次“通行证”只访问靠近边界的细胞。对于每个包含值为0的单元格，都使用值为-1的洪泛填充。这告诉你这个单元格值不同于1，并且与边界有连接。在此扫描之后，所有值为0的单元格都属于一个或多个孔。

To distinguish between different holes, you need the second scan. You then scan the remaining cells in the rectangle (1,1)x(n-2,n-2) you didn't scan yet. Whenever your scan hit a cell with value 0, you discovered a new hole. You then flood fill this hole with the integer of your choice to distinguish it from the others. After that you proceed with the scan until all cells have been visited.

要区分不同的孔，需要进行第二次扫描。然后扫描未扫描的矩形(1,1)x(n-2,n-2)中的剩余单元格。每当扫描命中一个值为0的单元时，就会发现一个新洞。然后用你选择的整数填充这个洞，以区别于其他数。然后继续扫描，直到所有单元格都被访问。

When done, you may replace the values -1 with 0 because there shouldn't be any 0 left.

完成后，可以将值-1替换为0，因为不应该有任何0。

This algorithm works, but is not as efficient as the other algorithm I propose. Its advantage is that it's simple and doesn't need an extra data storage to hold the segments, hole identification and eventual segment chaining reference.

这个算法是有效的，但是没有我提出的其他算法有效。它的优点是它简单，不需要额外的数据存储来保存段，孔识别和最终的段链接引用。