1254. 统计封闭岛屿的数目

1254. 统计封闭岛屿的数目

题目描述

二维矩阵 grid 由 0（土地）和 1（水）组成。

岛屿由四个方向相连的 0 组成。

封闭岛屿 是指一个完全被 1 包围，并且 不接触网格边界 的岛屿。

请你返回封闭岛屿的数目。

示例 1

text
输入：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]]
输出：2

示例 2

text
输入：grid = [[0,0,1,0,0],
			[0,1,0,1,0],
			[0,1,1,1,0]]
输出：1

示例 3

text
输入：grid = [[1,1,1,1,1,1,1],
             [1,0,0,0,0,0,1],
             [1,0,1,1,1,0,1],
             [1,0,1,0,1,0,1],
             [1,0,1,1,1,0,1],
             [1,0,0,0,0,0,1],
             [1,1,1,1,1,1,1]]
输出：2

约束

  • 1 <= grid.length, grid[0].length <= 100
  • 0 <= grid[i][j] <= 1

核心思路

这题看起来是在数岛屿，但和普通“岛屿数量”不一样的地方在于：

  • 只有 不接触边界 的岛屿才算

所以本题关键是先搞清楚：

  • 哪些陆地一定不可能是封闭岛屿的一部分？

答案是：

  • 所有和边界连通的陆地

因为只要一块陆地能够通过上下左右走到边界，那它就不是封闭的。

这题至少有两种常见做法：

  • 解法一：先淹掉边界连通陆地，再数剩余岛屿（推荐）
  • 解法二：DFS 返回当前岛屿是否封闭

解法一：先淹掉边界连通陆地，再数剩余岛屿

这是这题最经典、最推荐掌握的做法。

思路拆解

一个封闭岛屿一定满足：

  • 它和边界没有任何连通关系

所以我们可以反过来做：

  1. 先从边界出发，把所有与边界连通的陆地 0 全部淹掉（改成 1）
  2. 淹完之后，网格里剩下的所有陆地岛屿，就一定都是封闭岛屿
  3. 再去数这些剩余岛屿数量即可

这个思路非常像：

  • 先排除不合法部分
  • 再统计剩余合法部分

一步一步写出算法

第一步：定义 DFS 淹岛函数

ts
const dfs = (row: number, col: number): void => {
    if (
        row < 0 || row >= rows ||
        col < 0 || col >= cols ||
        grid[row][col] === 1
    ) {
        return
    }

    grid[row][col] = 1

    dfs(row - 1, col)
    dfs(row + 1, col)
    dfs(row, col - 1)
    dfs(row, col + 1)
}

它的作用是：

  • 把某块陆地以及和它连通的所有陆地全部改成水

第二步：先遍历边界，把边界连通陆地全淹掉

边界包括：

  • 第一行、最后一行
  • 第一列、最后一列

只要边界上某个位置是 0，就从那里 DFS。

第三步：再遍历整个网格统计剩余岛屿

如果某个位置还是 0：

  • 说明它不是边界连通陆地
  • 它属于一个封闭岛屿
  • 答案加一
  • 再 DFS 把整座岛淹掉，防止重复统计

代码实现（TypeScript）

ts
function closedIsland(grid: number[][]): number {
    const rows = grid.length
    const cols = grid[0].length

    const dfs = (row: number, col: number): void => {
        if (
            row < 0 || row >= rows ||
            col < 0 || col >= cols ||
            grid[row][col] === 1
        ) {
            return
        }

        grid[row][col] = 1
        dfs(row - 1, col)
        dfs(row + 1, col)
        dfs(row, col - 1)
        dfs(row, col + 1)
    }

    for (let row = 0; row < rows; row++) {
        if (grid[row][0] === 0) {
            dfs(row, 0)
        }
        if (grid[row][cols - 1] === 0) {
            dfs(row, cols - 1)
        }
    }

    for (let col = 0; col < cols; col++) {
        if (grid[0][col] === 0) {
            dfs(0, col)
        }
        if (grid[rows - 1][col] === 0) {
            dfs(rows - 1, col)
        }
    }

    let count = 0
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (grid[row][col] === 0) {
                count++
                dfs(row, col)
            }
        }
    }

    return count
}

复杂度分析

  • 时间复杂度：O(m * n)
  • 空间复杂度：O(m * n) 最坏递归栈

其中 m、n 分别是行数和列数。

这一解法的优缺点

优点：

  • 思路很巧
  • 非常经典
  • 最推荐

缺点：

  • 需要先想到“从边界反推”

解法二：DFS 返回当前岛屿是否封闭

这个做法更直接，是从每个岛屿本身出发判断。

思路拆解

我们从某个陆地 0 出发 DFS，判断整座岛是不是封闭的。

一个岛是否封闭，取决于：

  • 它在 DFS 过程中，有没有碰到边界外侧

所以 DFS 可以设计成返回布尔值：

  • true：从当前格子出发的这部分岛屿是封闭的
  • false：它和边界连通，不封闭

具体规则：

  1. 如果 DFS 走出了网格边界，说明这座岛接触边界，返回 false
  2. 如果遇到水 1，这条路对封闭性没有破坏，返回 true
  3. 否则继续四个方向搜索
  4. 只有四个方向都返回 true，整座岛才是封闭的

一步一步写出算法

第一步：定义 DFS 返回值含义

ts
const dfs = (row: number, col: number): boolean => {
    ...
}

表示：

  • 当前这块陆地所属的岛，从这里继续看是否封闭

第二步：处理越界情况

ts
if (row < 0 || row >= rows || col < 0 || col >= cols) {
    return false
}

只要越界，就说明接触外界，不封闭。

第三步：处理水域

ts
if (grid[row][col] === 1) {
    return true
}

遇到水不影响封闭性。

第四步：标记访问

ts
grid[row][col] = 1

第五步：递归四个方向

ts
const up = dfs(row - 1, col)
const down = dfs(row + 1, col)
const left = dfs(row, col - 1)
const right = dfs(row, col + 1)

return up && down && left && right

代码实现（TypeScript）

ts
function closedIsland(grid: number[][]): number {
    const rows = grid.length
    const cols = grid[0].length

    const dfs = (row: number, col: number): boolean => {
        if (row < 0 || row >= rows || col < 0 || col >= cols) {
            return false
        }

        if (grid[row][col] === 1) {
            return true
        }

        grid[row][col] = 1

        const up = dfs(row - 1, col)
        const down = dfs(row + 1, col)
        const left = dfs(row, col - 1)
        const right = dfs(row, col + 1)

        return up && down && left && right
    }

    let count = 0
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (grid[row][col] === 0 && dfs(row, col)) {
                count++
            }
        }
    }

    return count
}

复杂度分析

  • 时间复杂度：O(m * n)
  • 空间复杂度：O(m * n) 最坏递归栈

这一解法的优缺点

优点：

  • 更直接
  • 能很好锻炼 DFS 返回信息的写法

缺点：

  • 比第一种稍绕
  • 容易在返回值逻辑上写错

两种解法对比

解法时间复杂度空间复杂度特点
先淹边界连通陆地O(mn)O(mn)最经典，最推荐
DFS 直接判断封闭性O(mn)O(mn)更直接，但更绕

如果你是第一次做这题，建议优先掌握第一种“先排除边界连通陆地”的思路。

手动模拟一遍第一种解法

以：

text
grid = [[0,0,1,0,0],
        [0,1,0,1,0],
        [0,1,1,1,0]]

为例。

第一步：先看边界陆地

边界上的 0 包括：

  • 第一列的一些位置
  • 最后一列的一些位置
  • 第一行的一些位置

这些陆地都不是封闭岛屿的一部分。

从它们出发 DFS，把所有边界连通陆地都淹掉。

第二步：淹完后剩下什么？

中间那个位置：

text
(1, 2)

是一个 0，并且它四周都被 1 包围，也不接触边界。

所以这就是一座封闭岛屿。

第三步：统计结果

最终只剩这一座，所以答案是：

text
1

面试时最容易错的点

1. 这题和普通“岛屿数量”不一样

不是所有岛屿都算，只有：

  • 不接触边界的岛屿

才算封闭岛屿。

2. 只有上下左右算连通

不包含对角线。

3. 先处理边界是一种非常经典的思路

很多“被包围区域 / 封闭区域”问题，都可以先从边界反推。

4. DFS 返回布尔值时要小心逻辑

第二种解法里，只要一个方向越界了，整座岛就不封闭。

一句话总结

这题的本质是：

封闭岛屿 = 不和边界连通的陆地块。

  • 想写最经典解：用 先淹掉边界连通陆地
  • 想练 DFS 返回信息：用 DFS 判断整座岛是否封闭

推荐你最后记住的标准写法

如果你准备刷题，建议优先记下面这个版本：

ts
function closedIsland(grid: number[][]): number {
    const rows = grid.length
    const cols = grid[0].length

    const dfs = (row: number, col: number): void => {
        if (
            row < 0 || row >= rows ||
            col < 0 || col >= cols ||
            grid[row][col] === 1
        ) {
            return
        }

        grid[row][col] = 1
        dfs(row - 1, col)
        dfs(row + 1, col)
        dfs(row, col - 1)
        dfs(row, col + 1)
    }

    for (let row = 0; row < rows; row++) {
        if (grid[row][0] === 0) {
            dfs(row, 0)
        }
        if (grid[row][cols - 1] === 0) {
            dfs(row, cols - 1)
        }
    }

    for (let col = 0; col < cols; col++) {
        if (grid[0][col] === 0) {
            dfs(0, col)
        }
        if (grid[rows - 1][col] === 0) {
            dfs(rows - 1, col)
        }
    }

    let count = 0
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            if (grid[row][col] === 0) {
                count++
                dfs(row, col)
            }
        }
    }

    return count
}

因为这个版本：

  • 最经典
  • 最容易理解
  • 是这类“封闭区域”问题的通用模板之一