LeetCode 1162. 地图分析

2025-12-25 HGNULB 约 11 分钟

文章信息 8 个分类 4 个标签

分类

题目描述

✅ 1162. 地图分析

题意分析

给一个 n×n 的 01 网格，1 表示陆地、0 表示海洋。要找一个海洋格子，使它到最近陆地的曼哈顿距离最大，返回这个最大距离；如果网格里没有海洋或没有陆地，返回 -1。

题目要求的是一个「最大的最小值」：先对每个海洋格子求它到最近陆地的距离（取最小），再在所有海洋格子里取最大。两级极值的顺序不能颠倒。

距离定义是曼哈顿距离，等价于在四连通网格上只走上下左右的最短步数。这一点很关键——它意味着距离可以通过逐层扩散得到，不需要真的去算坐标差。

网格边长上限只有 100，格子总数一万，允许 $O(n^2)$ 甚至带小常数的算法，但不允许「对每个海洋格子分别搜一次最近陆地」这种 $O(n^4)$ 量级的做法。

边界就是题目明说的两种：全是陆地时没有海洋格子可选，全是海洋时不存在任何陆地，两种情况都返回 -1。

解法：多源广度优先搜索

核心思路

最直白的做法是对每个海洋格子跑一次 BFS 去找最近的陆地，取所有结果的最大值。它是对的，但每次 BFS 都可能扫遍整张图，总代价是格子数的平方级，一万个格子就是一亿次操作，而且不同海洋格子的搜索路径高度重叠，大量工作被重复做。

把方向反过来想：与其让每个海洋去找陆地，不如让所有陆地同时向外扩散。海水在时刻 1 淹没所有与陆地相邻的格子，时刻 2 淹没与这些格子相邻的格子……某个海洋格子第一次被淹没的时刻，恰好就是它到最近陆地的距离——因为扩散是按层同步推进的，任何更近的陆地都会更早把它淹到。

这就是多源 BFS：把所有陆地一次性放进初始队列，当作距离为 0 的「第 0 层」。它等价于虚构一个超级源点，向每块陆地连一条零权边，之后跑单源 BFS。

由此得到的不变量是：每一轮外层循环开始时，队列里恰好是所有到最近陆地距离等于当前 dist 的格子。第 0 层是全部陆地（距离 0），每轮把这一层的未访问邻居全部收进来构成下一层，距离随之加一。

既然队列按距离递增地逐层清空，最后一轮处理的那一层就是距离最大的格子，此时 dist 的值就是答案——不需要额外维护最大值变量。

标记已访问的方式是直接把海洋格子改写成 1。这既省掉了一个 visited 数组，也天然表达了「已经被淹没，不必再处理」的语义；代价是破坏了输入，实际工程中要先确认是否允许。

解题步骤

先遍历整张网格，把所有值为 1 的格子入队，同时用两个布尔量记录是否见过陆地、是否见过海洋。这一趟同时完成了「收集多源起点」和「判断退化情况」两件事，不用扫两遍。

若没有陆地或没有海洋，直接返回 -1。必须放在 BFS 之前：全陆地时队列非空但一步也扩不出去，全海洋时队列为空，两种情况都会让后面的 dist 取到毫无意义的值。

把 dist 初始化为 -1。因为循环的第一轮处理的是陆地层，它对应距离 0，先自增再处理正好把 dist 从 -1 抬到 0，让「层号」和「距离」始终对齐。

外层循环以队列非空为条件，每轮先取 size = queue.size() 固定本层元素个数，再让 dist 加一。取 size 快照是分层 BFS 的关键，不这么做队列会在循环中被新元素撑大，层的边界立刻失效。

内层弹出这 size 个格子，向四个方向扩展。越界的跳过，值已经是 1 的跳过——后者同时涵盖了「原本就是陆地」和「已经被淹过」两种情况。

对合法的海洋邻居，立刻把它改成 1 并入队。标记必须发生在入队瞬间：若等到出队再标记，同一个格子会被相邻的多个格子重复入队，队列规模膨胀，距离也可能被写错。

队列清空后返回 dist，它记录的是最后一层的层号，也就是离陆地最远的海洋格子的距离。

以 grid = [[1,0,1],[0,0,0],[1,0,1]] 走一遍。四个角是陆地，其余五格是海洋，两者都存在，不触发 -1。初始队列是 [(0,0),(0,2),(2,0),(2,2)]，dist = -1。

第一轮：size = 4，dist 变成 0，这一层是陆地本身，距离 0 合理。依次扩展四个角：(0,0) 把 (1,0) 和 (0,1) 淹掉并入队；(0,2) 把 (1,2) 淹掉，而 (0,1) 此时已经是 1 被跳过；(2,0) 把 (2,1) 淹掉，(1,0) 已被跳过；(2,2) 的两个邻居都已被淹。本轮结束队列是 [(1,0),(0,1),(1,2),(2,1)]。

第二轮：size = 4，dist 变成 1。这四个格子都与陆地相邻，距离确实是 1。扩展时它们的邻居大多已是 1，只有中心格 (1,1) 是海洋，被 (1,0) 第一次淹到并入队；随后 (0,1)、(1,2)、(2,1) 再看向中心时发现已是 1，跳过。本轮结束队列是 [(1,1)]。

第三轮：size = 1，dist 变成 2。中心格 (1,1) 的四个邻居全是 1，无法扩展。队列清空，循环结束。

返回 2。验证一下：中心格到四个角的曼哈顿距离都是 2，它到最近陆地的距离就是 2，而其它海洋格子距离都是 1，所以最大值确实是 2。

注意第二轮中心格只被入队一次：正是因为标记写在入队时刻，(0,1) 后来再看它时已经是 1。若把标记推迟到出队，中心格会被四个邻居各入队一次，dist 虽然仍对，但队列会白白膨胀四倍。

代码实现

class Solution {
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new ArrayDeque<>();
        boolean hasLand = false;
        boolean hasWater = false;

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

        if (!hasLand || !hasWater) {
            return -1;
        }

        int dist = -1;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int size = queue.size();
            dist++;
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] dir : dirs) {
                    int nr = cur[0] + dir[0];
                    int nc = cur[1] + dir[1];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                        continue;
                    }
                    if (grid[nr][nc] == 1) {
                        continue;
                    }
                    grid[nr][nc] = 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }

        return dist;
    }
}

func maxDistance(grid [][]int) int {
    n := len(grid)
    queue := make([][2]int, 0)
    hasLand := false
    hasWater := false

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

    if !hasLand || !hasWater {
        return -1
    }

    dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    dist := -1
    for head := 0; head < len(queue); {
        size := len(queue) - head
        dist++
        for i := 0; i < size; i++ {
            cur := queue[head]
            head++
            for _, d := range dirs {
                nr := cur[0] + d[0]
                nc := cur[1] + d[1]
                if nr < 0 || nr >= n || nc < 0 || nc >= n {
                    continue
                }
                if grid[nr][nc] == 1 {
                    continue
                }
                grid[nr][nc] = 1
                queue = append(queue, [2]int{nr, nc})
            }
        }
    }

    return dist
}

复杂度分析

时间复杂度：$O(n^2)$，每个格子最多入队一次、出队一次，出队时只检查固定的四个方向，总操作量与格子数成正比。

空间复杂度：$O(n^2)$，队列在最坏情况（几乎全是陆地）下要装下几乎所有格子；因为直接在 grid 上改写做标记，没有额外的 visited 数组。

关键点总结

「每个目标点到最近的某类源点的距离」这类问题，一律反过来做多源 BFS：把全部源点一次性入队当作第 0 层，一次扩散得到所有距离，避免逐点单源搜索的平方级重复。

多源 BFS 等价于建一个虚拟超级源点向所有真实源点连零权边，理解了这一点就能把它和单源 BFS 统一起来，也能自然推广到「多终点」「多起点多终点」的变体。

求「最大的最小距离」时，分层 BFS 的最后一层层号就是答案，不必额外维护最大值——因为队列是按距离严格递增清空的。

访问标记必须在入队时立刻打上；出队时才标记会让同一格子被多个邻居重复入队，最坏情况下队列规模成倍膨胀。

退化情况要在搜索开始前判掉：全陆地和全海洋都让「距离」失去意义，靠 BFS 结束后的值去兜底容易返回 0 这种看似合理实则错误的答案。

面试视角：面试官常追问三点——为什么不逐个海洋格子搜（复杂度），能不能不破坏输入（用 visited 数组或把已访问格子标成 2），以及有没有非 BFS 解法（两遍动态规划扫描，从左上到右下再从右下到左上递推最近距离，同样 $O(n^2)$ 但常数更小）。能主动给出 DP 解法会是明显加分。

易错点总结

错误写法：漏掉全陆地或全海洋的特判 → 用例 grid = [[1,1],[1,1]]，队列一开始就装满陆地，第一轮把 dist 抬到 0 后再无扩展，返回 0，正确答案是 -1。

错误写法：dist 初始化为 0 而不是 -1 → 用例 grid = [[1,0,1],[0,0,0],[1,0,1]]，陆地层被算成距离 1，最终返回 3，正确答案是 2。

错误写法：内层循环不取 size 快照，直接 while (!queue.isEmpty()) 遍历 → 用例同上，新入队的下一层格子被当成本层处理，层号与距离完全脱钩，返回 1。

错误写法：出队时才把格子标成 1 → 用例同上，中心格 (1,1) 被四个邻居各入队一次，队列规模成倍增长；在更大的网格上会明显变慢，且若同时把 dist 写进格子还会互相覆盖。

错误写法：把海洋格子入队而把陆地当作目标去搜 → 用例 grid = [[1,0,0],[0,0,0],[0,0,0]]，方向反了就退化成对每个海洋单独搜索，$O(n^4)$ 在 100×100 的网格上直接超时。

错误写法：方向数组写成八连通 → 用例 grid = [[1,0,0],[0,0,0],[0,0,1]]，斜向被当成一步，中心格距离算成 1，但曼哈顿距离下正确值是 2。

错误写法：越界判断写成 nr <= n 或 nc <= n → 用例任意 n×n 网格，访问下标 n 时 Java 抛越界异常、Go 直接 panic。

错误写法：判断陆地时写 if (grid[nr][nc] == 0) continue; 把条件写反 → 用例 grid = [[1,0,1],[0,0,0],[1,0,1]]，海洋被跳过、陆地被反复入队，队列永不为空，程序陷入死循环。

错误写法：BFS 结束后返回 dist - 1 或 dist + 1 去「修正」 → 用例 grid = [[1,0,1],[0,0,0],[1,0,1]]，返回 1 或 3，正确答案是 2；层号与距离的对齐应该靠初值 -1 保证，而不是最后拍脑袋加减。

错误写法：用最大值变量记录 Math.max(ans, dist) 却在陆地层也更新 → 逻辑上等价但容易写成在入队时更新，用例全陆地时返回 0 而非 -1。

错误写法：认为最优解一定在网格中心或四条边上，直接枚举少量候选点 → 用例 grid = [[0,0,0],[0,0,0],[0,0,1]]，最远点是左上角 (0,0) 距离 4，任何基于位置猜测的枚举都可能错过它。

相似题目

题目	难度	考察点
542. 01 矩阵	中等	同为多源扩散，但要输出每格的距离矩阵而非全局最大值
994. 腐烂的橘子	中等	多源扩散求总耗时，还需在结束后检查是否有格子永远扩散不到
127. 单词接龙	困难	图是隐式的，邻居靠改一个字母生成，需要预处理通配桶
433. 最小基因变化	中等	单源单终点，转移受合法基因库约束
752. 打开转盘锁	中等	状态是四位密码，起点即死亡状态是必考边界
773. 滑动谜题	困难	状态需序列化棋盘，扩展由空格可交换的位置决定
854. 相似度为 K 的字符串	困难	转移是交换字符，必须剪枝到只换能立刻归位的位置
909. 蛇梯棋	中等	编号到坐标的蛇形映射，落点可能被梯子改写
1091. 二进制矩阵中的最短路径	中等	八连通移动，且起点终点自身可能是障碍
1129. 颜色交替的最短路径	中等	状态要附加上一条边的颜色，是分层图的典型形态
1293. 网格中的最短路径	困难	附加维度是剩余可消除障碍数，同一格可被多次以不同状态访问
1298. 你能从盒子里获得的最大糖果数	困难	节点解锁依赖钥匙，需要缓存暂时打不开的盒子
1345. 跳跃游戏 IV	困难	相同值的下标全连边，用过一次必须清空该值的桶
1654. 到家的最少跳跃次数	中等	状态含「上一步是否后退」，还要推导搜索区间的上界
LCP 09. 最小跳跃次数	困难	需维护已扩展的最右边界，避免左向弹射重复入队
LCR 107. 01 矩阵	中等	542 的中文版，最适合拿来对照两遍 DP 的替代解法
LCR 108. 单词接龙	困难	127 的中文版，可练双向 BFS 的实现细节
LCR 109. 打开转盘锁	中等	752 的中文版，重点是死亡状态与起点重合的处理