LeetCode 1162. 地图分析 题目描述 你现在手里有一张大小为 n x n 的网格地图，网格上的每个单元格要么是陆地（用 0 表示），要么是海洋（用 1 表示）。网格以外的区域也视为海洋。你的任务是找出一个海洋单元格，它的最近陆地距离是最大的，并返回这个最大距离。 这里定义的距离是“曼哈顿距离”： (x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。 如果一个海洋单元格周围没有陆地，那么它的最近陆地距离被视为无穷大，但在这个问题中，我们规定此时其距离为 -1。实际上，这意味着如果地图上全是海洋或者全是陆地，都需要返回 -1。 解题过程 这个题目的核心是多源点最短路径问题。我们可以把所有的陆地看作是“源头”，海洋是“目的地”，要找到离所有源头“最远”的那个目的地。这非常适合用 广度优先搜索（BFS） 来解决，因为 BFS 天然地按照距离源点的层数（步数）向外扩展，能确保我们第一次访问到一个海洋单元格时，就是从某个陆地出发到达它的最短距离。 步骤详解 问题建模与初始化 我们将整个网格地图建模为一个二维数组 grid 。 为了记录每个单元格距离最近陆地的距离，我们初始化一个距离数组 dist ，大小与 grid 相同。初始时，所有海洋单元格的距离设为 -1 （表示尚未被访问/距离未知），所有陆地单元格的距离设为 0 。 我们创建一个队列 queue ，用于 BFS。 多源 BFS 的起点入队 标准的 BFS 通常从单一源点开始。这里是 多源 BFS 的经典应用。 我们遍历整个网格，将所有陆地单元格（ grid[i][j] == 1 ）的坐标 (i, j) 加入到队列 queue 中。这些陆地就是我们的“源头”。 同时，将这些陆地单元格在 dist 数组中的值更新为 0 。 执行 BFS 遍历 如果队列为空，有两种可能： 地图上全是陆地（所有单元格初始就是陆地，已全部入队并处理完毕）。 地图上全是海洋（没有陆地入队，队列初始为空）。 我们定义一个变量 maxDistance 来记录找到的最大距离，初始化为 -1 。 当队列不为空时，进行循环： a. 层级处理 ：由于 BFS 是一层一层扩散的，我们需要在每一轮开始前记录当前队列的大小 size 。这个 size 代表了当前“距离源头距离相同”的所有待处理单元格数量。 b. 处理当前层 ：循环 size 次，每次从队列头部取出一个单元格坐标 (x, y) 。 c. 探索四个方向 ：对于取出的单元格 (x, y) ，检查其上、下、左、右四个相邻的单元格 (nx, ny) 。 d. 判断与更新 ：检查相邻单元格 (nx, ny) 是否在地图范围内，并且它 必须是一个海洋单元格 （ grid[nx][ny] == 0 ） 且未被访问过 （ dist[nx][ny] == -1 ）。如果满足条件，说明我们找到了一个从某个陆地出发，到达这个海洋单元格的 最短路径 。 e. 计算距离 ：这个新发现的海洋单元格 (nx, ny) 的距离，就是其父节点 (x, y) 的距离加 1，即 dist[nx][ny] = dist[x][y] + 1 。 f. 更新答案 ：比较并更新全局最大距离 maxDistance = max(maxDistance, dist[nx][ny]) 。 g. 新点入队 ：将 (nx, ny) 加入队列，以便从它开始继续向更远的海洋扩散。 返回结果 当 BFS 结束后，队列为空。此时， maxDistance 中存储的值就是所有海洋单元格的最近陆地距离的最大值。 根据题意，如果地图上没有海洋（全是陆地），BFS 会立即结束， maxDistance 保持为初始值 -1 。如果地图上没有陆地（全是海洋），队列初始为空，BFS 不会执行， maxDistance 也为初始值 -1 。这两种情况都满足题目要求，直接返回 maxDistance 即可。 为什么这样做是对的？ BFS 保证了“最先访问到的距离就是最短距离”。我们从所有陆地（距离为0）同时开始 BFS，那么对于任何一个海洋单元格，第一次被访问到时，一定是离它最近的某个陆地找到了它，此时计算出的距离就是“最近陆地距离”。 因为所有陆地是同时开始扩散的，所以整个过程结束后，每个海洋单元格的 dist 值都已经被正确填充为最短距离。我们只需要在这个过程中记录下遇到的最大 dist 值。 复杂度分析 时间复杂度 ：O(N²)，其中 N 是网格的边长 n 。我们最多会遍历网格中的每个单元格一次。 空间复杂度 ：O(N²)，最坏情况下队列和距离数组都可能存储几乎所有的单元格（例如，当只有中心一块陆地时）。