如何计算2d数组中相同单元格的组？

Question

这里的（算上黑色的）例子：

输入：

输出：

5 4 // 5 groups (4 squares each) 
1 1 // 1 group containing 1 square 

现在，我想不出什么比一个不好受更好迭代。是否有可能以递归方式获得这些组？ 谢谢

Answer 1

将所有的黑色方块为节点。黑色方块之间的连接（如果方块彼此相邻）将成为边缘。

这给你一个graph。

A DFS在图中将会得到你所有的组。请注意，DFS本质上是递归的。

Answer 2

在开始时，每个细胞是“未访问”。

我将通过细胞，直到你遇到一个“未访问的”黑电池迭代。每一个白色的细胞你打到这一点

一旦你击中一个黑色的细胞，你可以“扩大”到所有方向，如果可能的话（类似于“填充”）。您尽可能长地展开，并将所有访问过的单元格标记为“已访问”。在你做完之后，你会计算你感染了多少黑细胞，并且你知道这个小组有多大。在检测到该组后，您继续下一个“未访问”黑色单元。

Answer 3

您可以使用算法为connected component labeling与4连接