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

约 6 分钟
文章信息 9 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 百度 快手 猿辅导
标签
数组 深度优先搜索 广度优先搜索 矩阵 并查集

题目描述

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

image-20260929000831871

image-20260929000831872

题意分析

0 表示陆地，1 表示水，沿上下左右连通的整块陆地构成一座岛。要求统计四周完全被水包围的岛屿数量，而不是其中的陆地格数；只要岛上有一个格子接触网格边界，整座岛就不封闭。

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

核心思路

[!blue]

封闭与否是整个连通块的性质，不能只看某个陆地格是否位于内部。一个内部格子也可能沿着陆地路径连到边界，因此先把所有与边界连通的陆地排除。

遍历四条边，从其中每个陆地格启动洪水填充 flood，把能够沿四方向到达的所有 0 改成 1。所有不封闭岛屿都包含边界陆地，一定会被某次填充清除；封闭岛屿不与边界连通，不会被这些搜索访问。

第一阶段结束后，剩余陆地都不接触边界。对任意剩余连通块，它周围若还有陆地就应属于同一块，块外相邻位置只能是水，因此整块一定封闭。随后扫描内部格子，每遇到一个尚未清除的 0 就计数一次，并填充它所属的整座岛，避免后续扫描重复计数。

两阶段共用同一个 flood：坐标越界或当前位置不是陆地就返回；否则先把当前位置改成水，再递归四个邻居。先标记能阻止相邻格子沿原路反复访问，使每个陆地格只展开一次。直接用网格保存访问状态，因此这个实现会修改输入。

解题步骤

  1. 遍历每行的最左、最右格子，以及每列的最上、最下格子，调用 flood 清除边界连通陆地。
  2. 将答案设为 0，扫描行 1..m-2、列 1..n-2 的内部位置。
  3. 每发现一个 0，答案加一，并调用 flood 清除整块陆地。
  4. 扫描完成后返回答案。

代码实现

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)$，m、n 为网格行列数。两阶段合计中，每个陆地格最多展开一次，每次只检查四个邻居。
  • 空间复杂度：$O(mn)$，最坏递归栈可包含整个连通块。

关键点总结

[!green]

  • 从边界可达的陆地恰好属于不封闭岛屿，先删除这部分后便只需统计剩余连通块。
  • 四角重复调用无妨，已淹没格直接返回。
  • 行数或列数不足 3 时没有内部候选，扫描循环不执行，自然返回 0。

易错点总结

[!yellow]

  • 把一当陆地，会反转整个题意。
  • 只处理角点，漏掉沿边其他开口。
  • 先递归再标记，相邻陆地可能互相无限访问。

相似题目

题目 难度 关联与区别
130. 被围绕的区域 中等 同样排除接触边界的区域，本题统计剩余封闭连通块，原题翻转内部区域。
200. 岛屿数量 中等 连通遍历相同，但本题0表示陆地且只数不接触边界的分量，原题统计全部岛屿。
695. 岛屿的最大面积 中等 用洪水填充标记网格连通分量；本题排除接触边界的零分量，该题统计各分量面积并取最大。
733. 图像渲染 简单 用洪水填充标记网格连通分量；本题排除接触边界的零分量，该题修改起点所属的同色分量。
1020. 飞地的数量 中等 用洪水填充标记网格连通分量；本题排除接触边界的零分量，该题从边界排除可逃离的陆地。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/79592558
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！