LeetCode 1254. 统计封闭岛屿的数目

2026-02-02 HGNULB 约 6 分钟

文章信息 9 个分类 5 个标签

分类

题目描述

✅ 1254. 统计封闭岛屿的数目

题意分析

网格里 0 是陆地、1 是水，注意这个取值和大多数岛屿题恰好相反，抄模板时最容易翻车。四连通的陆地组成一块岛屿，要求统计「四周完全被水包围」的岛屿有多少块。

「完全被水包围」这个说法换成可判定的形式就是：这块岛屿里不能有任何一个格子位于网格最外圈。因为一旦某个陆地格贴着边界，它朝网格外的那一侧就不存在水，自然不封闭。

约束信号是每个格子只有两种状态、连通性只看上下左右，这是标准的连通块遍历题。真正多出来的一层是：统计的不是连通块数量，而是「满足某个性质的连通块数量」，所以遍历过程中需要同时把性质算出来。

边界情形要想到：整个网格全是水时答案是 0；一块岛屿即使只有一个格子，只要它不在最外圈也算封闭；一块很大的岛屿只要有一个格子贴边，整块都不算。

解法：先淹没边界陆地，再统计内部岛屿

核心思路

封闭岛屿的反面更容易识别：只要一块陆地与边界上的陆地连通，它就一定不封闭。因此先从四条边上的所有陆地出发做 DFS，把这些连通块全部改成水；完成后，网格中还为 0 的陆地必然不接触边界，每个连通块就是一个封闭岛屿。

第二次扫描只看内部区域。每遇到一个尚未访问的 0，答案加一，再用同一个 flood 函数淹没整块岛屿，保证一个连通块只统计一次。

核心不变量是：边界处理结束后，所有与边界连通的陆地都已经变成 1；内部扫描过程中，已经计数的封闭岛屿也都已经变成 1。因此下一次遇到的 0 一定属于一个新的封闭岛屿。

解题步骤

定义 flood(row, col)：若坐标越界或当前格不是陆地 0，直接返回；否则先把当前格改为 1，再递归上下左右。

枚举第一列和最后一列，淹没边界陆地；再枚举第一行和最后一行。角落可能被调用两次，但第二次会因已是 1 立即返回。

只扫描下标范围 [1, m - 2] × [1, n - 2]。遇到 0，说明发现一块新的封闭岛屿，答案加一并调用 flood 消除整个连通块。

扫描结束后返回答案。

例如 [[1,1,1,1],[1,0,1,1],[1,1,1,0]] 中，右下角的 0 在第一阶段被边界 DFS 淹没；内部的 (1,1) 被保留，第二阶段只统计它一次，答案为 1。

代码实现

class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int row = 0; row < m; row++) {
            flood(grid, row, 0);
            flood(grid, row, n - 1);
        }
        for (int col = 0; col < n; col++) {
            flood(grid, 0, col);
            flood(grid, m - 1, col);
        }

        int ans = 0;
        for (int row = 1; row < m - 1; row++) {
            for (int col = 1; col < n - 1; col++) {
                if (grid[row][col] == 0) {
                    ans++;
                    flood(grid, row, col);
                }
            }
        }
        return ans;
    }

    private void flood(int[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length
                || grid[row][col] != 0) {
            return;
        }

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

func closedIsland(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    for row := 0; row < m; row++ {
        flood(grid, row, 0)
        flood(grid, row, n-1)
    }
    for col := 0; col < n; col++ {
        flood(grid, 0, col)
        flood(grid, m-1, col)
    }

    ans := 0
    for row := 1; row < m-1; row++ {
        for col := 1; col < n-1; col++ {
            if grid[row][col] == 0 {
                ans++
                flood(grid, row, col)
            }
        }
    }
    return ans
}

func flood(grid [][]int, row int, col int) {
    if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) {
        return
    }
    if grid[row][col] != 0 {
        return
    }

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

复杂度分析

时间复杂度：$O(mn)$。边界和内部各扫描一次，每个陆地格至多在一次 DFS 中被淹没。

空间复杂度：$O(mn)$。没有额外访问数组，但最坏情况下递归栈可包含所有陆地格。

关键点总结

把“不封闭”转化为“与边界连通”，先排除非法连通块，剩余部分就能直接套用岛屿计数。

flood 同时承担遍历和访问标记：先改成 1，再访问邻居，避免重复递归。

原地标记省去 visited 数组，但会修改输入；若后续还要使用原网格，需要先复制。

面试时应说明正确性分成两步：第一阶段删除且仅删除所有非封闭岛屿，第二阶段剩余的每个连通块都必然封闭。

易错点总结

本题 0 是陆地、1 是水，和常见岛屿模板相反。

必须处理四条边，不能只处理四个角；角落重复访问没有问题。

DFS 中必须先标记再递归，否则相邻陆地会互相递归直至栈溢出。

第二阶段不要再扫描边界。虽然第一阶段已清空边界陆地，但只扫内部更直接地表达算法前提。

连通规则只有上下左右，不包含对角线。

递归深度受语言栈限制；若网格规模显著增大，应改用显式栈或 BFS。

相似题目

题目	难度	考察点
130. 被围绕的区域	中等	反向从边界出发标记，再统一翻转剩余区域
200. 岛屿数量	中等	只数连通块，不需要 DFS 返回任何聚合信息
463. 岛屿的周长	简单	聚合量是边数，每遇到水或越界就累加 1
694. 不同岛屿的数量	中等	需要把遍历路径序列化成形状签名再去重
695. 岛屿的最大面积	中等	聚合量换成整数面积，返回值做求和而非逻辑与
1020. 飞地的数量	中等	同样排除贴边岛屿，但统计的是格子数而不是块数
LCR 105. 岛屿的最大面积	中等	面积版换号，适合做隔日默写复盘
面试题 16.19. 水域大小	中等	八连通版本，需要输出所有连通块大小并排序