我知道这个称号似乎有点暧昧，为此我已经连接，这将有助于清楚地了解问题的图像。我需要找到白色区域内的洞。有孔被定义为一个或多个单元格值为0的白色区域我的意思是得完全由单元格的值为封闭内'1'（例如，在这里我们可以看到三个孔标记为1，2和3 ）。我想出了一个pretty的天真的解决方案： 1.搜索整个矩阵的细胞与值'0' 2.运行DFS（洪水填充），这种细胞（黑的），当遇到和检查我们是否可以触摸主矩形区域的边界 3.如果我们能够DFS过程中触碰边界那就不是一个洞，如果我们不能达到的边界，然后它会被认为是空穴

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.

推荐答案

随着此时，floodFill，你已经有：沿着你的矩阵的边界运行，此时，floodFill它，也就是说， 改变全零（黑）到2（实心黑色）和那些以3（实心白色）;忽略2和3的那 来自较早此时，floodFill。

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.

例如你的矩阵，你从左上角开始，而此时，floodFill黑色带区区域 11.然后你向右移动，并发现你刚刚填写一个黑色的细胞。便又移动，并找到 白色区域，非常大的（在你的矩阵实际上所有的白色）。此时，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.

然后扫描矩阵：所有的领域，你会发现还是颜色0的是在黑洞。您可能还必须在白洞。

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，您可以设置 为2。当你发现1，就设置为3。

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

现在新的内边框上运行（这些细胞触及你刚才扫描的边界）。 零细胞触及2的成为2，1单元3接触成为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

小区A实际上是1。你检查它的邻居，你会发现1（但它也没用检查的是的，因为你还没有处理它，所以你可以不知道，如果它是一个1或应该是3 - 是哪种情况，顺便），2和2，一种2不能改变一个1，所以小区A保持1同样的问题也与小区B这又是一个1，等等。当你在小区C到达时，你会发现这是一个1，并具有3的邻居，所以它切换为3 ...但所有细胞从A到C现在应该切换的。

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.

最简单的，尽管不是最有效的，的方式来处理，这是顺时针扫描单元，它给你的错误的答案（C和D是1的，顺便说一句）

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

，然后扫描他们再次逆时针。现在，当你到达单元C，它具有3-邻居切换到3。接下来你检查单元D，其previous邻居是C，也就是现在的3，再这样ð切换到3。最后，你得到正确的答案

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.

如果您发现扫描的整个边框没有的甚至一度的切换单个单元格，用户可以暂停程序。检查这将花费你2（W * H）操作，所以如果有许多的漏洞。

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.

在最多W * H * 2个步骤，你应该做的。

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

您还可能要检查的渗流算法，并努力去适应一个。