计算位图中的“孔”数

Question

考虑一个单元格为0或1的MXN位图，'1'表示填充，“ 0”表示为空。

在位图中找到“孔”的数量，其中一个孔是空单元的连续区域。

例如，这有两个孔：

11111  
10101  
10101  
11111  

...只有一个：

11111  
10001  
10101  
11111

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

澄清: ：对角线不被认为连续，只有侧面的问题。

笔记: ：我正在寻找利用数据格式的东西。我知道如何将其转换为图形和[bd] fs，但这似乎过于杀伤。

Answer 1

你需要做 连接的组件标签 在你的图像上。您可以使用 两通算法 我上面链接的Wikipedia文章中描述了。考虑到您的问题的尺寸很小， 一通算法 可能就足够了。

你也可以使用 BFS/DFS 但是我建议上述算法。

Answer 2

这似乎是不连接集合数据结构的很好使用。
将位图转换为2D数组
循环通过每个元素
如果当前元素是0，请与它的“以前”的空邻居（已经访问过）合并
如果没有空的邻居，请将其添加到自己的集合中

然后只计算集合的数量

Answer 3

使用表格和位操作可能会获得优势。

例如，可以在256个元素表中查找8个像素的整行，因此通过单个查找获得了1 XN中的孔数。然后，可能有一些256XK元素的查找表，其中k是上线中的孔配置数，扭曲了完整孔的数量和下一个孔配置。那只是一个主意。