algorithm - 统计位图中 "holes"的个数

Question

考虑一个 MxN 位图，其中单元格为 0 或 1。“1”表示填充，“0”表示空。

找出位图中“孔”的数量，其中孔是空白单元格的连续区域。

例如，这有两个洞:

11111  
10101  
10101  
11111  

...而这只有一个:

11111  
10001  
10101  
11111

当 M 和 N 都在 1 和 8 之间时，最快的方法是什么？

澄清:对角线不被认为是连续的，只有边邻接很重要。

注意:我正在寻找利用数据格式的东西。我知道如何将其转换为图形并 [BD]FS 但这似乎有点过分了。

Answer 1

你需要做 connected component labeling在你的形象上。您可以使用 Two-pass algorithm我在上面链接的维基百科文章中有描述。鉴于您的问题规模较小，One-pass algorithm可能就足够了。

你也可以使用 BFS/DFS但我会推荐上述算法。