如何計算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連接