Description
給定一個二維網格
grid，0代表陸地、1代表水域。封閉島嶼是完全被水域包圍的陸地群（不接觸邊界）。回傳封閉島嶼的數量。
Example:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2
Intuition#
先淹沒所有接觸邊界的島嶼，再計算剩餘島嶼數。
- 接觸邊界的陸地不可能是封閉島嶼的一部分
- 先從邊界的
0（陸地）開始 DFS 淹沒 - 然後計算剩餘的陸地連通區域數
Approaches#
1: 先淹邊界再計數#
- 概念: 先 DFS 淹沒邊界相連的陸地，然後計算剩餘島嶼數
- 時間複雜度:
O(m * n) - 空間複雜度:
O(m * n)（遞迴堆疊）
class Solution {
fun closedIsland(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
fun dfs(i: Int, j: Int) {
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != 0) return
grid[i][j] = 1
dfs(i + 1, j); dfs(i - 1, j); dfs(i, j + 1); dfs(i, j - 1)
}
// 淹沒邊界島嶼
for (i in 0 until m) { dfs(i, 0); dfs(i, n - 1) }
for (j in 0 until n) { dfs(0, j); dfs(m - 1, j) }
// 計算封閉島嶼
var count = 0
for (i in 1 until m - 1) {
for (j in 1 until n - 1) {
if (grid[i][j] == 0) {
count++
dfs(i, j)
}
}
}
return count
}
}⭐2: 一次 DFS 判定#
- 概念: DFS 時同時判斷是否碰到邊界，若碰到則不計數
- 時間複雜度:
O(m * n) - 空間複雜度:
O(m * n)
class Solution {
fun closedIsland(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
var count = 0
fun dfs(i: Int, j: Int): Boolean {
if (i < 0 || i >= m || j < 0 || j >= n) return false // 碰到邊界
if (grid[i][j] != 0) return true
grid[i][j] = 1
// 不能短路，必須遍歷完整座島嶼
val a = dfs(i + 1, j)
val b = dfs(i - 1, j)
val c = dfs(i, j + 1)
val d = dfs(i, j - 1)
return a && b && c && d
}
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 0 && dfs(i, j)) count++
}
}
return count
}
}🔑 Takeaways#
- Pattern: 邊界排除法 – 先處理邊界相連的區域，再計數內部區域
- 關鍵技巧: 注意此題
0是陸地、1是水域（與常見題目相反）；一次 DFS 判定時不能短路