1020. Number of Enclaves

Medium

Description

給定一個二維網格 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#

先淹沒所有與邊界相連的陸地，再計算剩餘陸地格子數。

與邊界相連的陸地可以走出網格，不算飛地
先從邊界的 1 開始 DFS/BFS 淹沒
計算剩餘 1 的個數即為答案

Approaches#

⭐1: DFS 淹沒邊界#

概念: 從邊界所有 1 開始 DFS 標記，最後計算未被標記的 1 數量
時間複雜度: O(m * n)
空間複雜度: 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 淹沒邊界#

概念: 用 BFS 替代 DFS，避免遞迴堆疊溢出
時間複雜度: O(m * n)
空間複雜度: 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: 邊界淹沒法 – 先清除邊界相連區域，剩餘即為飛地
關鍵技巧: 與 1254 Number of Closed Islands 類似，差別在本題計算格子數而非島嶼數