MediumRating 1659
1254. Number of Closed Islands
arraydepth-first-searchbreadth-first-searchunion-findmatrix
解題說明
Number of Closed Islands
題目描述：
給定一個二維網格 grid，其中 0 表示陸地，1 表示水。「封閉島嶼」是指完全被水包圍的陸地區域（不觸碰邊界）。回傳封閉島嶼的數量。
解題思路： 分兩步驟處理：
- 排除邊界相連的陸地：先對所有與邊界相連的陸地（0）進行 DFS/BFS，將它們標記為已訪問（例如改為 1），因為這些陸地不可能構成封閉島嶼。
- 計算封閉島嶼：再遍歷整個網格，對每個未訪問的陸地（仍為 0）啟動 DFS/BFS，每啟動一次就計數一個封閉島嶼，同時標記整個連通區域為已訪問。
這種「先淘汰邊界、再計數內部」的思路簡潔有效。
C++ 解法
複雜度分析
時間複雜度：O(m * n) — 每個格子最多被訪問一次。
空間複雜度：O(m * n) — DFS 遞迴堆疊在最壞情況下的深度。
虛擬碼
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其他解法
BFS 方法：用佇列代替遞迴進行廣度優先搜尋，避免遞迴深度過大導致的堆疊溢出。時間空間複雜度相同，但在大網格上更安全。
Union-Find 方法：將所有陸地格子用 Union-Find 合併，邊界相連的陸地標記為非封閉。最後統計未與邊界合併的連通分量數。時間 O(mnα(m*n))，略複雜但適合需要動態查詢的場景。
延伸思考
- 若網格的值可以動態變化（陸地變水或水變陸地），如何高效維護封閉島嶼數量？
- 本題中 0 是陸地、1 是水，與經典島嶼問題相反。這類「反轉定義」的題目有哪些常見陷阱？
- 若要同時回傳每個封閉島嶼的面積，如何修改演算法？