LeetCode 1020. 飞地的数量

约 8 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 华为 美团
标签
数组 深度优先搜索 广度优先搜索 矩阵 并查集

题目描述

✅ 1020. 飞地的数量

image-20260928225422401

image-20260928225422402

题意分析

网格中 1 表示陆地，0 表示海洋。只能沿上下左右相邻的陆地移动，统计无法走出网格边界的陆地格子数。这里统计的是格子数量，不是飞地连通块的数量。

解法：边界 BFS

核心思路

[!blue]

一条离开网格的陆地路径，最后必然经过某个边界陆地；反过来，能到达边界陆地的格子也一定能走出去。因此，“可以离开”恰好等价于“与边界上的陆地连通”。

从四条边上的所有陆地同时开始 BFS，沿四个方向清除与它们连通的陆地。搜索结束后，所有能离开的格子都已变成 0，剩下的 1 不可能有通向边界的陆地路径，逐个计数就是答案。

当前代码在出队时才把格子改成 0，所以角点或多个邻居可能重复加入同一坐标。出队时先跳过已经为 0 的格子，保证每格只展开一次。每格至多被四个邻居及边界收集加入常数次，重复项不会改变线性复杂度；网格本身同时充当访问标记。

解题步骤

  1. 扫描左右两列、上下两行，把边界陆地的坐标放入队列。
  2. 取出一个坐标；若已为 0，跳过这个重复项，否则将其改为 0。
  3. 检查上下左右四个邻居，把仍在网格内且值为 1 的格子加入队列。
  4. 队列耗尽后重新扫描网格，返回剩余值为 1 的格子数。

代码实现

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

        Deque<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 1) {
                queue.offer(new int[] {
                    i,
                    0
                });
            }

            if (grid[i][n - 1] == 1) {
                queue.offer(new int[] {
                    i,
                    n - 1
                });
            }
        }

        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                queue.offer(new int[] {
                    0,
                    j
                });
            }

            if (grid[m - 1][j] == 1) {
                queue.offer(new int[] {
                    m - 1,
                    j
                });
            }
        }

        int[] dx = {
            1,
            -1,
            0,
            0
        };
        int[] dy = {
            0,
            0,
            1,
            -1
        };

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            // 同一坐标可能重复入队，只在首次出队时展开。
            if (grid[x][y] == 0) {
                continue;
            }

            // 清除已确认能经陆地抵达边界的格子。
            grid[x][y] = 0;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                    queue.offer(new int[] {
                        nx,
                        ny
                    });
                }
            }
        }

        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }

        return count;
    }
}

func numEnclaves(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])

    queue := make([][2]int, 0)

    for i := 0; i < m; i++ {
        if grid[i][0] == 1 {
            queue = append(queue, [2]int{
                i,
                0,
            })
        }
        if grid[i][n-1] == 1 {
            queue = append(queue, [2]int{
                i,
                n - 1,
            })
        }
    }
    for j := 0; j < n; j++ {
        if grid[0][j] == 1 {
            queue = append(queue, [2]int{
                0,
                j,
            })
        }
        if grid[m-1][j] == 1 {
            queue = append(queue, [2]int{
                m - 1,
                j,
            })
        }
    }

    dx := []int{
        1,
        -1,
        0,
        0,
    }
    dy := []int{
        0,
        0,
        1,
        -1,
    }

    head := 0
    for head < len(queue) {
        cur := queue[head]
        head++

        x, y := cur[0], cur[1]
        // 同一坐标可能重复入队，只在首次出队时展开。
        if grid[x][y] == 0 {
            continue
        }
        // 清除已确认能经陆地抵达边界的格子。
        grid[x][y] = 0

        for k := 0; k < 4; k++ {
            nx := x + dx[k]
            ny := y + dy[k]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1 {
                queue = append(queue, [2]int{
                    nx,
                    ny,
                })
            }
        }
    }

    count := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                count++
            }
        }
    }

    return count
}

复杂度分析

  • 时间复杂度：$O(mn)$，其中 m、n 为网格行列数；每个格子最多展开一次，重复入队次数也有常数上界。
  • 空间复杂度：$O(mn)$ 上界，队列占用；Go 下标队列还保留已经处理的坐标。

关键点总结

[!green]

  • 边界连通性按四个方向，斜对角不相连。
  • 单行、单列全部在边界上，答案零。
  • 边界收集中的角点、单行或单列可能重复入队，出队检查负责跳过已处理项。

易错点总结

[!yellow]

  • 只收集上下边会漏掉左右出口。
  • 当前出队标记写法去掉重复检查，会反复展开同一格。
  • 用八方向搜索，会把仅斜接边界的内部陆地错误清除。

相似题目

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