1905. Count Sub Islands

Medium
Description

給定兩個 m x n 的二維網格 grid1 和 grid2。grid2 中的一座島嶼被稱為「子島嶼」，若該島嶼的所有陸地格子在 grid1 中也是陸地。回傳 grid2 中子島嶼的數量。

Example:

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]] Output: 3

Intuition#

在 grid2 做 DFS 找島嶼時，同時檢查每個陸地格子在 grid1 是否也是陸地。

  • 遍歷 grid2 的每座島嶼
  • DFS 過程中，若任一陸地格子在 grid1 中是水域，則該島嶼不是子島嶼
  • 注意：即使發現不是子島嶼，仍需繼續 DFS 完成標記，避免重複計算

Approaches#

1: 先排除再計數#

  • 概念: 先把 grid2 中在 grid1 為 0 的陸地格子淹沒（DFS 標記為 0），再計算 grid2 剩餘島嶼數
  • 時間複雜度: O(m * n)
  • 空間複雜度: O(m * n)（遞迴堆疊）
class Solution {
    fun countSubIslands(grid1: Array<IntArray>, grid2: Array<IntArray>): Int {
        val m = grid1.size
        val n = grid1[0].size

        // 先淹沒 grid2 中不可能是子島嶼的陸地
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid2[i][j] == 1 && grid1[i][j] == 0) {
                    flood(grid2, i, j)
                }
            }
        }

        // 計算剩餘島嶼數
        var count = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid2[i][j] == 1) {
                    count++
                    flood(grid2, i, j)
                }
            }
        }
        return count
    }

    private fun flood(grid: Array<IntArray>, i: Int, j: Int) {
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == 0) return
        grid[i][j] = 0
        flood(grid, i + 1, j)
        flood(grid, i - 1, j)
        flood(grid, i, j + 1)
        flood(grid, i, j - 1)
    }
}

⭐2: 一次 DFS 同時判定#

  • 概念: DFS 遍歷 grid2 島嶼時，同時追蹤是否所有格子在 grid1 也是陸地
  • 時間複雜度: O(m * n)
  • 空間複雜度: O(m * n)（遞迴堆疊）
class Solution {
    fun countSubIslands(grid1: Array<IntArray>, grid2: Array<IntArray>): Int {
        val m = grid1.size
        val n = grid1[0].size
        var count = 0

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid2[i][j] == 1) {
                    if (dfs(grid1, grid2, i, j)) count++
                }
            }
        }
        return count
    }

    private fun dfs(grid1: Array<IntArray>, grid2: Array<IntArray>, i: Int, j: Int): Boolean {
        if (i < 0 || i >= grid2.size || j < 0 || j >= grid2[0].size || grid2[i][j] == 0) return true
        grid2[i][j] = 0
        var isSub = grid1[i][j] == 1
        // 必須繼續 DFS 所有方向，不能短路
        isSub = dfs(grid1, grid2, i + 1, j) && isSub
        isSub = dfs(grid1, grid2, i - 1, j) && isSub
        isSub = dfs(grid1, grid2, i, j + 1) && isSub
        isSub = dfs(grid1, grid2, i, j - 1) && isSub
        return isSub
    }
}

🔑 Takeaways#

  • Pattern: 雙網格比對 – 在一個網格搜尋的同時參考另一個網格
  • 關鍵技巧: DFS 判定時不能短路（&& 短路），必須完整遍歷整座島嶼才能正確標記；將 isSub 放在 && 右側可避免短路問題