我知道标题似乎有点模棱两可，因此我附上了一张图片，这将有助于清楚地理解问题。我需要在白色区域内找到洞。一个洞被定义为白色区域内的一个或多个值为“0”的单元格我的意思是它必须被值为“1”的单元格完全包围（例如，在这里我们可以看到三个标记为 1、2 和 3 的洞）。我想出了一个非常幼稚的解决方案： 1. 在整个矩阵中搜索值为 '0' 的单元格 2. 当遇到这样的单元格（黑色单元格）时运行 DFS（Flood-Fill）并检查我们是否可以触摸主矩形区域的边界 3. 如果我们在 DFS 期间可以触及边界，那么它不是一个洞，如果我们不能到达边界，那么它将被认为是一个洞
现在，这个解决方案有效，但我想知道是否有任何其他有效/快速的解决方案来解决这个问题。
请让我知道你的想法。谢谢。
使用您已经拥有的填充填充：沿着矩阵的边界运行并填充填充，即将所有零（黑色）更改为 2（填充黑色）和一个更改为 3（填充白色）；忽略来自较早洪水填充的 2 和 3。
例如，对于您的矩阵，您从左上角开始，将区域 11 的区域填充为黑色。然后向右移动，找到刚刚填充的黑色单元格。再次向右移动，找到一个非常大的白色区域（实际上是矩阵中的所有白色区域）。填满它。然后你再次向右移动，另一个新的黑色区域沿着整个上边界和右边界延伸。四处走动，您现在会发现之前填充的两个白色单元格并跳过它们。最后你会发现沿着底部边框的黑色区域。
计算您找到并设置的颜色数量可能已经提供了有关矩阵中是否有孔的信息。
否则，或者要找到它们的位置，请扫描矩阵：您找到的所有颜色仍为 0 的区域都是黑色的洞。你可能也有白色的洞。
另一种方法，一种“被逮捕的洪水填充”
在第一个矩阵的边界周围运行。在您找到“0”的地方，您设置为“2”。在您找到“1”的地方，您设置为“3”。
现在绕过新的内边界（那些接触您刚刚扫描的边界的单元格）。接触 2 的零单元格变为 2，接触 3 的 1 单元格变为 3。
您将不得不扫描两次，一次顺时针，一次逆时针，检查当前单元格“向外”和“之前”的单元格。那是因为你可能会发现这样的事情：
22222222222333333
2AB11111111C
31
单元格 A 实际上是 1。您检查它的邻居并找到 1（但检查它是没用的，因为您还没有处理它，所以您不知道它是 1 还是应该是 3 - 就是这种情况，顺便说一句），2 和 2。A 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 步，你应该完成。
您可能还想检查渗透算法并尝试调整该算法。
制作某种“LinkedCells”类来存储相互链接的单元格。然后按从左到右从上到下的顺序逐个检查单元格，对每个单元格进行以下检查：如果它的相邻单元格是黑色的 - 将此单元格添加到该单元格的组中。否则，您应该为此单元创建新组。您应该只检查顶部和左侧邻居。
UPD： 对不起，我忘了合并组：如果两个相邻的单元格都是黑色的并且来自不同的组 - 你应该将这些组合并为一个。
如果您的“LinkedCells”类连接到边缘，它应该有一个标志。默认情况下为 false，如果您将边缘单元添加到该组，则可以将其更改为 true。在合并两个组的情况下，您应该将新标志设置||为以前的标志。最后，您将拥有一组组，每个具有错误连接标志的组将是“洞”。
该算法将是 O(x*y)。
您可以将网格表示为图形，其中单个单元格作为顶点，相邻顶点之间出现边。然后，您可以使用广度优先搜索或深度优先搜索从侧面的每个单元格开始。由于您只会找到连接到侧面的组件，因此尚未访问的黑色单元格是孔。您可以再次使用搜索算法将孔划分为不同的组件。
编辑：最坏情况的复杂性必须与单元格的数量成线性关系，否则，给算法一些输入，检查哪些单元格（因为你是次线性的，会有很大的未访问点）算法没有调查并放一个那里的洞。现在你得到了一个算法没有找到其中一个漏洞的输入。
您的算法在全球范围内都可以。这只是通过将洪水填充探索与单元扫描合并来优化它的问题。这只会最小化测试。
大体思路是在扫描表的同时逐行执行洪水填充探索。因此，您将拥有多个必须跟踪的并行洪水填充。
然后表格从上到下逐行处理，每一行从右到左处理。顺序是任意的，如果您愿意，可以颠倒。
让段标识一行中值为 0 的连续单元格序列。您只需要值为 0 的第一个和最后一个单元格的索引来定义一个段。正如您可能猜到的那样，一个段也是一个正在进行的洪水填充。因此，我们将在段中添加一个标识号，以区分不同的洪水填充。
该算法的好处是您只需要跟踪第 i 行和第 i-1 行中的段及其标识号。因此，当您处理第 i 行时，您将拥有在第 i-1 行中找到的段列表及其关联的标识号。
然后，您必须处理第 i 行和第 i-1 行中的段连接。我将在下面解释如何提高效率。
现在你必须考虑三种情况：
发现第 i 行中的段未连接到第 i-1 行中的段。为其分配一个新的孔标识（递增整数）。如果它连接到表格的边框，则将此数字设为负数。
发现第 i-1 行中的段未连接到第 i-1 行中的段。你找到了一个洞的最低部分。如果它的标识号为负，则它连接到边界，您可以忽略它。否则，恭喜你，你找到了一个洞。
发现第 i 行中的一个段连接到第 i-1 行中的一个或多个段。将所有这些连接段的标识号设置为最小的标识号。请参阅以下可能的用例。
第 i-1 行：2 333 444 111 第 i 行：**** *** ***
第 i 行中的段都应该得到值 1，标识相同的洪水填充。
通过保持从左到右的顺序并比较段索引，可以有效地匹配第 i 行和第 i-1 行中的段。
首先按最低起始索引处理段。然后检查它是否连接到另一行的起始索引最低的段。如果否，则处理案例 1 或 2。否则继续识别连接的段，跟踪最小的标识号。当没有找到更多的连接线段时，将第i行中找到的所有连接线段的标识号设置为最小的标识值。
连通性测试的索引比较可以通过将 (first-1,last) 存储为段定义来优化，因为段可以通过它们的角连接。然后，您可以直接比较索引裸值并检测重叠段。
选择最小标识号的规则可确保您自动获得连接段的负数，并且至少有一个连接到边界。它传播到其他段和洪水填充。
这是一个很好的编程练习。您没有指定所需的确切输出。所以这也留作练习。
此处描述的蛮力算法如下。
我们现在假设我们可以在单元格中写入一个不同于 0 或 1 的值。
您需要一个洪水填充函数，该函数接收一个单元格的坐标开始，一个整数值写入所有保持值为 0 的连接单元格。
由于您只需要考虑孔洞（值为 0 的单元格被值为 1 的单元格包围），因此您必须使用两遍。
第一次访问仅接触边界的单元格。对于每个包含值 0 的单元格，使用值 -1 进行泛洪填充。这告诉您该单元格的值不同于 1，并且与边界有连接。在此扫描之后，所有值为 0 的单元都属于一个或多个孔。
要区分不同的孔，您需要进行第二次扫描。然后扫描矩形 (1,1)x(n-2,n-2) 中尚未扫描的剩余单元格。每当您的扫描击中值为 0 的单元格时，您就会发现一个新洞。然后，你用你选择的整数填充这个洞，以将它与其他人区分开来。之后，您继续扫描，直到访问了所有单元格。
完成后，您可以将值 -1 替换为 0，因为不应该剩下任何 0。
该算法有效，但不如我提出的其他算法有效。它的优点是简单，不需要额外的数据存储来保存段、孔标识和最终的段链接参考。