給定一個二維網格
grid，1代表陸地、0代表水域。求無法通過任意步數走到邊界的陸地格子數量（即被完全包圍的陸地格子數）。
Example:
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3
Intuition
TIP
先淹沒所有與邊界相連的陸地，再計算剩餘陸地格子數。
- 與邊界相連的陸地可以走出網格，不算飛地
- 先從邊界的
1開始 DFS/BFS 淹沒 - 計算剩餘
1的個數即為答案
Approaches
⭐ 1. DFS Flood from Border — O(m * n) / O(m * n)
- Idea: 從邊界所有
1開始 DFS 標記，最後計算未被標記的1數量 - Time:
O(m * n) - Space:
O(m * n)（遞迴堆疊）
class Solution {
fun numEnclaves(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] != 1) return
grid[i][j] = 0
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 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == 1) count++
}
}
return count
}
}2. BFS Flood from Border — O(m * n) / O(m * n)
- Idea: 用 BFS 替代 DFS，避免遞迴堆疊溢出
- Time:
O(m * n) - Space:
O(m * n)
class Solution {
fun numEnclaves(grid: Array<IntArray>): Int {
val m = grid.size
val n = grid[0].size
val queue = ArrayDeque<IntArray>()
val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
for (i in 0 until m) {
for (j in 0 until n) {
if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 1) {
grid[i][j] = 0
queue.add(intArrayOf(i, j))
}
}
}
while (queue.isNotEmpty()) {
val (r, c) = queue.removeFirst()
for ((dr, dc) in dirs) {
val nr = r + dr
val nc = c + dc
if (nr in 0 until m && nc in 0 until n && grid[nr][nc] == 1) {
grid[nr][nc] = 0
queue.add(intArrayOf(nr, nc))
}
}
}
var count = 0
for (i in 0 until m) for (j in 0 until n) if (grid[i][j] == 1) count++
return count
}
}🔑 Takeaways
- Pattern: 邊界淹沒法 — 先清除邊界相連區域，剩餘即為飛地
- Key trick: 與 1254 Number of Closed Islands 類似，差別在本題計算格子數而非島嶼數