MediumRating 1679

1905. Count Sub Islands

arraydepth-first-searchbreadth-first-searchunion-findmatrix

解題說明

Count Sub Islands

題目描述：給定兩個 m × n 的二進位矩陣 grid1 和 grid2。如果 grid2 中的一個島嶼所覆蓋的所有陸地格子在 grid1 中也都是陸地，則稱該島嶼是 grid1 的「子島嶼」。求 grid2 中子島嶼的數量。

解題思路：使用 DFS 遍歷 grid2 中的每個島嶼。

對 grid2 中每個未訪問的陸地格子（值為 1）發起 DFS。
DFS 過程中，檢查該島嶼的每個格子在 grid1 中是否也是陸地。如果有任何一個格子在 grid1 中是水，則這個島嶼不是子島嶼。
注意：即使發現不是子島嶼，DFS 也要繼續完成（標記整個島嶼為已訪問），否則同一島嶼的其他部分會被誤認為新島嶼。
統計所有是子島嶼的數量。

C++ 解法

複雜度分析

時間複雜度：O(m × n) — 每個格子最多訪問一次。

空間複雜度：O(m × n) — 遞迴棧的最壞深度為 m × n。

虛擬碼

1. Initialize count = 0
2. For each cell (i, j) in grid2:
   a. If grid2[i][j] == 1:
      - Run DFS from (i, j)
      - If DFS returns true (it's a sub-island), count++
3. dfs(i, j):
   a. If out of bounds or grid2[i][j] == 0, return true
   b. Mark grid2[i][j] = 0
   c. isSub = (grid1[i][j] == 1)
   d. Recursively DFS all 4 neighbors, AND results with isSub
      (MUST visit all neighbors, no short-circuit)
   e. Return isSub
4. Return count

其他解法

BFS O(m × n)：用 BFS 替代 DFS 遍歷每個島嶼，邏輯相同但避免了深遞迴的棧溢出風險。對於非常大的矩陣更安全。

Union-Find O(m × n × α)：先在 grid2 上用 Union-Find 識別所有島嶼，再檢查每個島嶼的所有格子是否都在 grid1 中。需要額外的映射記錄每個連通分量是否滿足條件。

延伸思考

如果 grid1 中的島嶼是子島嶼的超集，能否有效找出 grid1 中多出的陸地？
如果擴展到三維（3D 網格），如何修改 DFS？
如果要計算「部分重疊」的島嶼數（至少一個格子重疊），如何修改判斷條件？

Count Sub Islands — CaffeCode