1. For each cell on the grid border:
a. If it is land (0), run DFS to flood-fill it to water (1)
2. Initialize count = 0
3. For each cell in the entire grid:
a. If it is land (0):
- Run DFS to flood-fill the entire connected component
- Increment count
4. Return count題目描述:
給定一個二維網格 grid,其中 0 表示陸地,1 表示水。「封閉島嶼」是指完全被水包圍的陸地區域(不觸碰邊界)。回傳封閉島嶼的數量。
解題思路: 分兩步驟處理:
這種「先淘汰邊界、再計數內部」的思路簡潔有效。
時間複雜度:O(m * n) — 每個格子最多被訪問一次。
空間複雜度:O(m * n) — DFS 遞迴堆疊在最壞情況下的深度。
BFS 方法:用佇列代替遞迴進行廣度優先搜尋,避免遞迴深度過大導致的堆疊溢出。時間空間複雜度相同,但在大網格上更安全。
Union-Find 方法:將所有陸地格子用 Union-Find 合併,邊界相連的陸地標記為非封閉。最後統計未與邊界合併的連通分量數。時間 O(mnα(m*n)),略複雜但適合需要動態查詢的場景。