題目描述:給定 '1'(陸地)和 '0'(水)組成的二維網格,計算島嶼的數量(相鄰陸地組成一個島嶼)。
解題思路:每當發現一個未訪問的 '1',計數加一,然後用 DFS(或 BFS)洪水填充(flood fill)標記整個島嶼為已訪問(將 '1' 改為 '0' 或使用訪問標記陣列)。繼續掃描直到遍歷完整個網格。
時間複雜度:O(m × n) — 每個格子最多被訪問一次。
空間複雜度:O(m × n) — 遞迴棧深度(最壞情況下整個網格是一個島嶼)。
1. count = 0
2. For each cell (r, c) in grid:
a. If grid[r][c] == '1':
- count++
- DFS/BFS from (r, c), marking all connected '1's as visited
3. Return countDFS (遞迴) O(m×n) 時間,O(m×n) 空間:遞迴訪問相鄰陸地,同 BFS 邏輯 — 常數略異。
並查集 (Union-Find) O(m×n α(m×n)) 時間,O(m×n) 空間:合併相鄰陸地至同一分量,計數分量數 — 邏輯清晰。