计算位图中"孔"的数量

Question

考虑一个MxN位图,其中单元格为0或1."1"表示填充,"0"表示空.

找到位图中"孔"的数量,其中孔是空单元的连续区域.

例如,这有两个漏洞:

......这只有一个:

什么是最快的方式,当M和N都在1到8之间？

澄清:对角线不被认为是连续的,只有侧面邻接很重要.

注意:我正在寻找利用数据格式的东西.我知道如何将其转换为图形和[BD] FS,但这看起来有点过分.

Answer 1

您需要在图像上进行连接组件标记.您可以使用上面链接的维基百科文章中描述的两遍算法.鉴于问题的规模很小,One-pass算法可能就足够了.

您也可以使用BFS/DFS,但我建议使用上述算法.

Answer 2

这似乎是一个很好的使用不相交的数据结构. 如果当前元素为0,
则将位图转换为
通过每个元素的2d数组循环
,
如果它没有空邻居,则将其与其"先前"空邻居(已访问过)的集合合并,将其添加到其自己的集合中

然后只计算套数