algorithm - 给定一个二维数组，找到 "holes"

Question

识别完全被 1 包围的 0(不需要对角线覆盖)。在下面的示例中，大小应为 3。

二维数组中可能有任意数量的“孔”。

[[1,0,1,1],
 [1,1,1,1],
 [1,0,0,1],
 [1,0,1,1],
 [1,1,1,0]]

注意:我在这里看到问题:Finding holes in 2d point sets? ，但我对那里的答案不是很满意。

Answer 1

您的“孔”实际上是由网格形成的图形中零的连接分量。每个元素都有四个邻居。查找 connected components与 BFS或 DFS ，选择最大的一个，或者将它们相加。该算法在 O(N) 中运行，其中 N 是矩阵中元素的数量。

您还可以使用更具体的 labeling algorithm ，适用于这些类型的图表，通常出现在图像中。标签还将为您枚举所有连接的组件。

如果你对连接的组件不感兴趣，那些没有完全被组件包围的组件，就像这样:

[[1,0,1,1],
 [1,1,1,1],
 [1,0,0,1],
 [0,0,1,1],  // <-- Note zero in the beginning
 [1,1,1,0]]

您可以使用零边界扩展您的矩阵，如下所示:

[[0,0,0,0,0,0]
 [0,1,0,1,1,0],
 [0,1,1,1,1,0],
 [0,1,0,0,1,0],
 [0,0,0,1,1,0],
 [0,1,1,1,0,0],
 [0,0,0,0,0,0]]

然后忽略外层连通分量。在这个例子中，没有更多的组件，所以答案是零。