地图分析 · 0 到最近 1 的最大距离

虾皮（Shopee）笔试编程题 · 核心代码模式（原题：LeetCode 1162 地图分析）

题目描述

给定一个 m × n 的二维网格 grid，其中每个格子的取值是 0 或 1：

• 0 表示海洋；
• 1 表示陆地。

对每一个海洋格子（0），计算它到**最近的陆地格子（1）**的距离。这里的距离指最短路径长度：只能沿着上、下、左、右四个方向移动，每移动一格距离 +1。

请返回所有海洋格子中，这个距离的最大值。如果网格上只有陆地或者只有海洋，请返回 -1。

输入格式

• 一个 m × n 的二维数组 grid，元素为 0 或 1。

输出格式

• 一个整数：所有海洋格子到最近陆地距离的最大值；若没有海洋或没有陆地，返回 -1。

示例

示例 1

输入：

grid = [
  [1, 0, 1],
  [0, 0, 0],
  [1, 0, 1]
]

输出：

2

说明： 海洋格子 (1,1) 到最近的陆地（四角的 1 之一）距离为 2，是全部海洋格子中的最大值。

示例 2

输入：

grid = [
  [1, 0, 0],
  [0, 0, 0],
  [0, 0, 0]
]

输出：

4

说明： 最远的海洋格子是右下角 (2,2)，到陆地 (0,0) 的距离为 4。

示例 3

输入：

grid = [[0, 0, 0], [0, 0, 0]]

输出：

-1

说明： 全是海洋，没有任何陆地，返回 -1。

---

解题思路

第一步：理解问题本质

对每个海洋格子，要求"到最近陆地的最短距离"，再在这些距离中取最大值。即：

答案 = max( 每个 0 格子 到最近 1 格子的最短路径长度 )

这是一个"网格图上的多源最短路"问题。多个"源点"（所有陆地）同时向外扩展，计算每个点到最近源点的距离。

第二步：暴力解法

思路： 枚举每个海洋格子，再遍历所有陆地格子，直接计算曼哈顿距离取最小。

def maxDistance(self, grid):
    m, n = len(grid), len(grid[0])
    lands = [(i, j) for i in range(m) for j in range(n) if grid[i][j] == 1]
    if not lands or len(lands) == m * n:
        return -1
    ans = -1
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                d = min(abs(i - x) + abs(j - y) for x, y in lands)
                ans = max(ans, d)
    return ans

为什么不够好：

• 每个海洋格子都要扫一遍所有陆地格子，时间复杂度 O(m²·n²)；
• 网格较大时（如 m=n=100、200）完全不可行；
• 大量重复计算：不同的海洋格子到同一块陆地的路径被反复求解。

第三步：优化解法（对每个海洋做单源 BFS）

思路： 对每个海洋格子做一次 BFS，找到最近陆地。

• 对每个 0 格子，从它出发 BFS，第一个访问到的 1 格子的层数就是它到最近陆地的距离；
• 对所有结果取最大值。

特点：

• 单个 BFS 最坏 O(m·n)，共 O(m·n) 个海洋格子，总复杂度 O(m²·n²)，依然不可行；
• 但揭示了关键点：BFS 的层数天然等于最短距离。

第四步：最优解法（多源 BFS）

思路： 把所有陆地格子同时作为 BFS 的起点，一起向外逐层扩散。

• 第一层扩散到的海洋格子，距离为 1；
• 第二层扩散到的海洋格子，距离为 2；
• 依此类推，一个格子被访问到时所在的层数，就是它到最近陆地的距离。

为什么一定是"最近"？因为所有陆地同时从 0 开始扩散，BFS 保证每个格子第一次被访问到时就走了最短路径（BFS 的最短路性质）。因此：

• 最后一个被访问到的海洋格子，层数最大；
• 该层数就是题目要求的最大距离。

实现细节：

1. 把所有值为 1 的格子全部入队；
2. 若队列为空（没有陆地）或队列长度等于 m*n（全是陆地），返回 -1；
3. 按层 BFS：每处理完一层，distance += 1；
4. 访问到海洋格子时原地标记为 1（相当于"被陆地感染"），避免重复入队；
5. BFS 结束后返回 distance。

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码191 帧 · 录制输入 [ [1, 0, 1], [0, 0, 0], [1, 0, 1] ]

from collections import deque
from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 多源 BFS：把所有陆地格子(1)都作为起点入队
        q = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    q.append((i, j))

        # 没有陆地，或没有海洋，都不存在合法答案
        if not q or len(q) == m * n:
            return -1

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        distance = -1  # 记录当前 BFS 层数（即到最近陆地的距离）

        while q:
            distance += 1                     # 进入下一层
            for _ in range(len(q)):           # 只处理当前层
                x, y = q.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    # 是未访问的海洋格子，就"被陆地感染"，入队
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0:
                        grid[nx][ny] = 1      # 原地标记为已访问
                        q.append((nx, ny))

        # 最后一层处理完的格子，就是离所有陆地最远的海洋格子
        return distance

笔试环境为"核心代码模式"，只需实现类方法；本地测试时在 if __name__ == "__main__": 中补充测试用例即可（见 code-training/shoppee/shoppee_max_distance_to_land.py）。

---

示例推演

以示例 1为例，grid = [[1,0,1],[0,0,0],[1,0,1]]：

初始：
1 0 1
0 0 0
1 0 1

初始化： 四个角的陆地全部入队。

第 1 层（distance = 0）： 处理四块陆地，把相邻的海洋格子 (0,1)、(1,0)、(1,1)、(1,2)、(2,1) 全部标记并入队。

1 1 1
1 1 1
1 1 1   （标记为 1 的格子：最近距离 = 1）

第 2 层（distance = 1）： 处理上述 5 个格子，它们的邻居都已被标记，没有新格子入队。

第 3 层（distance = 2）： 队列为空，循环结束。

返回 2。

验证：(1,1) 到最近的陆地确实需要 2 步（如 (1,1) → (1,0) → (0,0)），且它是所有海洋格子中距离最远的，答案正确。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力（枚举 0 遍历所有 1）	O(m²·n²)	O(m·n)	每个海洋格子扫一遍所有陆地
单源 BFS（对每个 0）	O(m²·n²)	O(m·n)	每个海洋格子做一次 BFS
多源 BFS（最优）	O(m·n)	O(m·n)	每个格子最多入队一次

其中 m、n 分别为网格的行数与列数。

---

易错点总结

1. 忘了"没有陆地/没有海洋"返回 -1

• 没有陆地：q 为空；
• 没有海洋：len(q) == m*n。 两个条件都要判断，缺一不可。

2. 层数计数错误

distance 的初始值和自增时机要配合好：先自增再处理当前层，返回的就是"最后一个格子的层数"。若初始设为 0 会导致结果偏大 1。

3. 按层处理 vs 逐格处理

如果不在 for _ in range(len(q)) 中按层推进，而是一次只 popleft 一个格子，distance 就无法表示"层数"，结果会变成总步数。必须按层批量处理。

4. 原地标记的语义

把访问过的海洋格子直接改成 1 是合法的（题目允许修改），但要注意：如果后续代码还需要区分"原始陆地"和"被感染格子"，就要用独立的 visited 数组。

5. 对角线不算距离

题目只允许上下左右移动，不能走对角线。四个方向写好即可。

---

扩展思考

• 多源 BFS 的本质： 把"多个源点求最近距离"转化为"从超源点（一个虚拟节点连向所有陆地）出发的单源 BFS"，层数即距离。这是网格 BFS 的通用套路。
• DP 两遍扫描： 本题也可以用两次动态规划（左上→右下、右下→左上）在 O(m·n) 内求出每个 0 到最近 1 的距离，不需要显式队列，可作为理解"动态规划 vs BFS"的对比练习。
• 相关题目： 542. 01 矩阵（求每个 0 到最近 1 的距离矩阵）、994. 腐烂的橘子（多源 BFS + 最短时间）、286. 墙与门（多源 BFS）。
• 面试追问： 如果要求返回"最远海洋格子的坐标"而不是距离，只需在最后一层出队时记录坐标即可。

---

相关题目

• 542. 01 矩阵 — 多源 BFS / DP 求距离矩阵
• 994. 腐烂的橘子 — 多源 BFS 求最短时间
• 1162. 地图分析 — 本题原题
• 286. 墙与门 — 多源 BFS