LeetCode 1162. 地图分析

约 7 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 华为 微软
标签
数组 动态规划 广度优先搜索 矩阵

题目描述

✅ 1162. 地图分析

image-20260928230156501

image-20260928230156502

题意分析

网格中一表示陆地，零表示海洋。先对每一个海洋格计算它到最近陆地的曼哈顿距离，再从这些最近距离中取最大值，返回最远离任何陆地的海洋格的距离。

要取的是“到最近陆地的距离”的最大值，不是任意一对海陆之间的最大距离。距离按上下左右移动的步数计算，每次移动一格算一步，不走对角线；如果没有陆地或没有海洋，按题意返回 -1。

解法：多源广度优先搜索

核心思路

[!blue]

逐个海洋格寻找最近陆地会反复搜索相同区域。反过来，把全部陆地同时放进 BFS 的初始队列，视为距离零的一层，再一层层向相邻海洋扩散，就可以一次得到所有海洋格到最近陆地的距离。

BFS 按距离从小到大处理。若某个海洋格第一次从距离 d 的格子被发现，就存在一条长为 d + 1 的海陆路径；如果它还有更短的路径，那条路径的前一格必然在更早的层被处理，早就应该发现它。因此第一次发现对应的距离就是最近距离，而不必区分是由哪片陆地到达。

每层处理之前先固定当前队列大小，保证新加入的格子都留到下一层。距离变量从 -1 开始，每处理一层先加一，所以第一次处理全部陆地时距离恰好为零；之后每扩散一层，距离增加一。队列耗尽时，最后一层就是海洋格中最大的最近距离。

同一个海洋格可能被多个来源发现，必须在入队时就把它标记为已访问。代码直接将其改成一，既作为访问标记，也避免再次入队；因此会修改输入网格。所有陆地已经在初始队列中，后续只加入尚未访问的海洋。

网格没有不可通过的障碍，只要同时存在海陆，全部海洋最终都能被扩散到。全海或全陆要在搜索前单独返回 -1，否则没有有效的海洋到陆地距离可以取最大值。

解题步骤

  1. 扫描网格，把所有陆地坐标加入队列，并记录是否存在海洋与陆地。
  2. 任意一种不存在时返回 -1，否则令 dist = -1。
  3. 每轮固定当前待处理层的大小，并将 dist 加一。
  4. 处理本层每个格子的四个相邻位置，跳过越界、陆地和已经访问过的位置。
  5. 将新发现的海洋立刻标记为一，再加入队列，留给下一层处理。
  6. 队列为空后返回 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²)。网格有 n² 个格子，每个格子最多入队一次，每次检查四个方向。
  • 空间复杂度：O(n²)。队列最坏保存线性数量的网格坐标，访问标记直接复用并改写原网格。

关键点总结

[!green]

  • 多个陆地同时作为零距离源点，第一次到达才表示到所有陆地的最近距离。
  • BFS 层号给出每个海洋格的最小距离，最后一层给出这些最小距离的最大值。
  • 入队即标记，使不同方向和不同陆地不会重复加入同一格。
  • 固定每层数量才能把当前层与新发现的下一层分开。

易错点总结

[!yellow]

  • 只从一块陆地开始：得到的是到该起点的距离，未必是到最近陆地的距离。
  • 把陆地初始层记为一：所有海洋距离都会多算一步，陆地距离应为零。
  • 遍历本层时动态扩大处理数量：会把下一层提前处理，层号不再对应真实距离。
  • 出队才标记：同一格可能在出队前被多个邻居重复加入，造成冗余扩展。
  • Go 队列计入已经处理的历史前缀：当前层长度应取 len(queue) - head，而不是队列总长度。
  • 忽略原网格被改写：一同时表示原陆地与已访问海洋，搜索结束后原始海陆信息不再保留。

相似题目

题目 难度 关联与区别
542. 01 矩阵 中等 多源BFS得到每格到最近陆地或0的距离，本题只取海洋格距离最大值。
934. 最短的桥 中等 两题都在岛屿间扩散，但最短桥取两个岛的最小间距，本题取海洋到最近陆地的最大距离。
994. 腐烂的橘子 中等 从多个起点同时进行逐层广度优先搜索；本题从全部陆地求海洋的最近距离，该题模拟腐烂波及相邻橘子的分钟数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/52002973
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！