algorithm - 给定二维数组，找到“孔”

标识完全被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?，但我对那里的答案不太满意。

最佳答案

你的“洞”实际上是由网格形成的图中零的连接组件。每个元素有四个邻居使用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]]

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

关于algorithm - 给定二维数组，找到“孔”，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25029990/