給定兩個
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
TIP
在 grid2 做 DFS 找島嶼時，同時檢查每個陸地格子在 grid1 是否也是陸地。
- 遍歷
grid2的每座島嶼 - DFS 過程中，若任一陸地格子在
grid1中是水域，則該島嶼不是子島嶼 - 注意：即使發現不是子島嶼，仍需繼續 DFS 完成標記，避免重複計算
Approaches
1. Exclude then Count — O(m * n) / O(m * n)
- Idea: 先把
grid2中在grid1為0的陸地格子淹沒（DFS 標記為 0），再計算grid2剩餘島嶼數 - Time:
O(m * n) - Space:
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. Single DFS (decide in one pass) — O(m * n) / O(m * n)
- Idea: DFS 遍歷
grid2島嶼時，同時追蹤是否所有格子在grid1也是陸地 - Time:
O(m * n) - Space:
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: 雙網格比對 — 在一個網格搜尋的同時參考另一個網格
- Key trick: DFS 判定時不能短路（
&&短路），必須完整遍歷整座島嶼才能正確標記；將isSub放在&&右側可避免短路問題