arrays - 如何计算二维数组中相同单元格的组？

Question

这是示例（计算黑色）：

输入：

输出：

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

现在，我想不出比迭代痛苦更好的方法了。是否有可能以递归方式获得这些组？谢谢

Answer 1

将所有黑色方块设置为节点。黑色方块之间的连接（如果方块彼此相邻）将是一条边。

这给了你一个图表。

图中的DFS将为您提供所有组。请注意，DFS 本​​质上是递归的。

Answer 2

一开始，每个单元格都是“未访问的”。

我会遍历单元格，直到遇到“未访问”的黑色单元格。您在该点之前击中的每个白色单元格

一旦你击中一个黑色单元格，如果可能的话，你将它“扩展”到所有方向（类似于“floodfilling”）。您尽可能扩展并将所有访问过的单元格标记为“已访问”。在你这样做之后，你计算你感染了多少黑细胞，你就知道这个群体有多大了。检测到该组后，您继续进入下一个“未访问”的黑色单元。

Answer 3

您可以使用具有 4 连接性的连接组件标记算法