LeetCode 1020. 飞地的数量

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

题目描述

✅ 1020. 飞地的数量

题意分析

给定一个只含 0 和 1 的二维网格，1 表示陆地、0 表示海洋。可以从任意一个陆地格子出发，每次向上下左右四个方向之一移动一格，也可以选择走出网格边界。题目要问的是：有多少个陆地格子，无论怎么走都走不出网格。

「走不出去」这个说法容易让人以为要对每个陆地格子分别做一次可达性搜索，但换个说法就清楚多了：一个陆地格子能走出边界，当且仅当它经过若干次相邻陆地移动之后，能抵达某个位于网格最外圈的陆地格子。反过来，走不出去的格子就是那些和外圈陆地完全不连通的陆地。于是问题从「逐个判断」变成了「整体划分」，答案等于陆地总数减去与边界连通的陆地数。

约束里给的信息也支持这个方向：行列数都不超过 500，总格子数最多 25 万，允许一次线性规模的遍历，但不允许对每个格子各做一次搜索那样的平方级做法。移动只有四个方向，说明连通性按四连通定义，斜对角不算相邻。

边界情况需要留意：网格可能全是海洋，答案为 0；也可能所有陆地都贴着边界，答案同样为 0；只有一行或一列时，所有格子都在边界上，答案必然是 0。

解法：边界 BFS

核心思路

最朴素的想法是遍历每一个陆地格子，从它出发做一次搜索看能不能碰到边界，能碰到就跳过、碰不到就计数。这样做逻辑上没错，但每个格子都要付出一次全图搜索的代价，最坏情况是 $O((mn)^2)$，在 500 乘 500 的规模下完全不可接受。瓶颈在于这些搜索之间存在大量重复——同一个连通块里的所有格子，答案本来就是一样的，却被反复算了很多遍。

关键观察是把方向反过来：与其从内部往外找出路，不如从外面往里灌水。所有能走出边界的陆地，必定属于某个「触碰到最外圈」的连通块；而这些连通块，从最外圈的陆地格子出发做一次搜索就能全部覆盖到。也就是说，只要以全部边界陆地为起点做一次多源搜索，把访问到的格子统统抹成海洋，剩下还是 1 的格子就恰好是答案。这样每个格子最多被访问常数次，代价降到 $O(mn)$。

不变量可以这样写：在搜索过程中，凡是被从队列里取出并置 0 的格子，都是与网格边界连通的陆地；搜索结束时，网格中仍为 1 的格子集合，恰好等于与边界不连通的陆地集合。初始入队的都是边界上的陆地，显然满足前半句；每次扩展只走向相邻的陆地格子，连通性可以传递，所以性质在整个过程中保持。搜索结束意味着再没有可从边界抵达的陆地，因此剩下的 1 一个不多一个不少，直接数一遍就是答案。

这里还有一个小技巧值得点出：算法直接把原网格当作访问标记数组来用，把访问过的陆地改写成 0。这既省掉了一个同样大小的布尔数组，又让最后的统计变得极其简单——只要数还剩多少个 1。

解题步骤

第一步，取出行数 m 和列数 n，并准备一个队列。用队列做广度优先扩散而不是递归深度优先，是因为最坏情况下连通块可能覆盖整张网格，递归深度会达到 25 万层而爆栈，显式队列则把这部分开销转移到了堆上。

第二步，把所有边界上的陆地格子作为搜索起点入队。具体是先扫最左列和最右列的每一行，再扫最上行和最下行的每一列，只要值为 1 就入队。之所以要把全部边界陆地一次性放进队列，是因为它们地位平等、都是「可以走出去」的源头，多源广度优先搜索天然支持同时从多个起点扩散，不需要一个个单独跑。四个角会被重复入队两次，但后面的判重逻辑会消化掉，不影响正确性。

第三步，准备方向数组 dx = {1, -1, 0, 0} 与 dy = {0, 0, 1, -1}，配合下标 k 从 0 到 3 循环，就能简洁地枚举下、上、右、左四个邻居。用方向数组而不是写四段重复代码，是为了让边界检查只写一次。

第四步，循环从队首取出格子 (x, y)。先判断 grid[x][y] == 0，若成立就直接跳过。这一步是必需的去重：同一个格子可能被多个邻居先后放进队列，等它第二次出队时早已被处理并置 0，此时必须跳过，否则它的邻居会被重复入队，队列规模会不受控地膨胀。

第五步，把 grid[x][y] 置 0，表示这个格子已经确认与边界连通并且已被处理。这一步同时完成了「标记已访问」和「从答案中扣除」两件事，正是复用原网格带来的便利。

第六步，枚举四个方向得到邻居 (nx, ny)，只有在下标合法且 grid[nx][ny] == 1 时才入队。入队前先检查是否为 1，可以挡掉海洋格子和已处理格子，大幅减少无效入队；下标合法性检查必须写在数组访问之前，否则会越界。

第七步，队列耗尽后，对整张网格做一次全量扫描，统计仍为 1 的格子数量并返回。此时网格里的 1 全部是与边界不连通的陆地，也就是题目要的飞地。

以 grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 走一遍：先收集边界陆地，第 0 列上 (1,0) 为 1 入队，其余边界格子都是 0，队列初始为 [(1,0)]。出队 (1,0)，它当前是 1，置 0；检查四个邻居，(2,0) 为 0、(0,0) 为 0、(1,1) 为 0、(1,-1) 越界，没有新元素入队。队列为空，扩散结束。最后统计整张网格，还剩下 (1,2)、(2,1)、(2,2) 三个 1，它们组成的连通块完全被海洋包围，碰不到任何边界，返回 3。再看一个全部相连的例子 grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]：边界扫描中最上行的 (0,1) 和 (0,2) 都是 1，双双入队；出队 (0,1) 置 0，其邻居 (0,2) 为 1 入队；出队 (0,2) 置 0，邻居 (1,2) 入队；随后 (1,2)、(2,2) 依次出队置 0；再次出队的 (0,2) 因为已经是 0 被跳过。最终网格全为 0，返回 0，符合「所有陆地都能走到最上行然后走出去」的直觉。

代码实现

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 为网格的行数与列数。每个陆地格子最多被置 0 一次，置 0 后它的四个方向只会被枚举一次；虽然同一格子可能被多次入队，但入队次数被邻居数限制在常数倍以内，加上最后一次全量统计扫描，总代价与格子总数成正比。
  • 空间复杂度：$O(mn)$。访问标记直接复用了原网格没有额外开销，但队列在极端情况下（例如整张网格都是陆地）会同时容纳与格子数同阶的坐标，这是主要的空间占用。

关键点总结

  • 「从内部找出路」难算就「从外部灌水」：当每个元素都要判断能否抵达某类特殊位置时，把搜索方向反转成从特殊位置出发做一次多源扩散，能把平方级的重复搜索压成一次线性遍历，这是网格题里最常复用的换位思考。
  • 多源广度优先搜索就是把全部起点先塞进队列：不需要为每个源单独跑一遍，也不需要额外的层次编号，初始队列里放几个点，扩散就自动从几个点同时展开。
  • 允许修改输入时，原地改写是最省事的访问标记：把访问过的 1 抹成 0，既避免申请等大的布尔数组，又让最终统计退化成简单计数；但要在面试中主动说明这会破坏入参，若调用方不接受就改用独立的 visited 数组。
  • 出队时补一次状态检查是队列去重的兜底：入队前判断只能挡住当时的重复，一个格子仍可能被多个邻居在同一轮塞进队列，出队时再确认一次才能保证每个格子只被真正处理一次。
  • 面试视角：先点破「能走出去等价于与边界连通」这层转化，再说明为什么选广度优先而不是递归深度优先（500 乘 500 的连通块会让递归栈深达 25 万），最后主动补充并查集解法——把所有边界陆地并入一个虚拟节点，最终统计不与该节点同根的陆地数，用来展示对连通性问题的多种建模能力。

易错点总结

  • 边界收集只扫了最上行和最下行：grid = [[0,0,0],[1,1,0],[0,0,0]] 会漏掉最左列的 (1,0)，那条本可走出去的陆地被当成飞地，返回 2 而不是 0。
  • 出队后忘记 if (grid[x][y] == 0) continue;：grid = [[1,1],[1,1]] 中同一个格子被多个邻居重复入队，第二次出队时会再次枚举邻居，队列不断膨胀，规模大时直接内存超限。
  • 入队时不置 0 也不做出队检查，只在处理完才标记：grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0],[0,0,0,0]] 会让同一格子被反复处理，时间从线性退化到指数级增长的入队次数。
  • 越界检查写在数组访问之后：把条件写成 grid[nx][ny] == 1 && nx >= 0 && ...，grid = [[1]] 在计算上方邻居 (-1, 0) 时立刻抛出越界异常。
  • 方向数组配错，把 dx 和 dy 的元素凑成了斜向：grid = [[1,0],[0,1]] 会把两个对角陆地当成连通，误判 (1,1) 也能走出边界，返回 0 而不是 1。
  • 忘记单行或单列的退化情形：grid = [[1,1,1]] 中每个格子都在边界上，如果只按「非边界格子才可能是飞地」去遍历内部却漏掉了边界收集，会返回错误的非零值。
  • 统计阶段沿用了搜索前保存的陆地总数再做减法，但搜索中改写了原网格：grid = [[0,1,0],[0,1,0],[0,0,0]] 里先算总数 2、再用被清空后的网格算连通数 2，两个口径不一致，得到 0 与实际答案 1 不符。
  • 直接用递归深度优先搜索处理超大连通块：grid 为 500 乘 500 全 1 时递归深度达 25 万层，Java 默认栈直接溢出。
  • 假设 grid[0] 一定存在：传入 grid = [] 时 grid[0].length 抛出越界异常，虽然本题约束保证行数至少为 1，但把这行代码搬到别处就会出问题。
  • 认为把访问过的陆地改成 2 之类的第三种值更安全却忘了同步统计条件：grid = [[0,1,0],[1,1,1],[0,1,0]] 若标记为 2 而统计时仍数「非 0」的格子，会把已连通的陆地也算进答案。

相似题目

题目 难度 考察点
130. 被围绕的区域 中等 同为边界反向扩散，但要求原地把未连通区域翻转而非计数
200. 岛屿数量 中等 统计连通块个数，重点在外层遍历触发新搜索的时机
305. 岛屿数量 II 困难 陆地动态增加，必须用并查集维护连通块数量的增量变化
417. 太平洋大西洋水流问题 中等 从两组边界分别灌水后求交集，扩散还受高度单调性约束
463. 岛屿的周长 简单 只需数陆地与海洋的相邻边，可不做搜索直接逐格累加
694. 不同岛屿的数量 中等 需要给连通块编码形状并去重，考察路径序列化
695. 岛屿的最大面积 中等 每个连通块单独计数并取最大值，而非全局统计
827. 最大人工岛 困难 需先给连通块编号并记面积，再枚举把某个 0 翻成 1 后的合并结果
994. 腐烂的橘子 中等 同为多源广度优先搜索，但要按层统计扩散所需的轮数
1254. 统计封闭岛屿的数目 中等 数的是完全封闭的连通块个数而不是格子数，且陆地与海洋取值相反
LCR 105. 岛屿的最大面积 中等 面积最大值问题的另一份题面，适合练习递归与迭代两种写法
面试题 16.19. 水域大小 中等 连通性按八方向定义，且要求把所有面积排序后输出