1162. 地图分析

ITCharge大约 4 分钟

---

1162. 地图分析

标签：广度优先搜索、数组、动态规划、矩阵
难度：中等

题目链接

1162. 地图分析 - 力扣

题目大意

描述：给定一个 $n \times n$ 的网格 $grid$ ，每个格子要么是海洋（ $0$ ），要么是陆地（ $1$ ）。

要求：找出一个海洋格子，这个海洋格子离它最近的陆地格子的距离是最大的，并返回这个最大距离。如果网格上全是海洋或全是陆地，返回 $-1$ 。

这里的距离是「曼哈顿距离」—— 也就是 $|x_0 - x_1| + |y_0 - y_1|$ ，可以理解为「从一个格子走到另一个格子，最少需要走多少步（只能上下左右走）」。

说明：

$n == grid.length$ 。
$n == grid[i].length$ 。
$1 \le n \le 10^{3}$ 。
$grid[i][j]$ 不是 $0$ 就是 $1$ 。

示例：

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋格子 (1, 1) 距离所有陆地格子都是 2 步，没有比它更远的海洋格子了。

示例 2：

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋格子 (2, 2) 离陆地格子最远，要走 4 步。

解题思路

思路 1：多源 BFS（从所有陆地同时向外扩散）

这道题可以想象成「在海洋里，哪个位置离陆地最远」。一个直观的想法是：从所有陆地同时向四周的海洋一格一格地「扩散」，每一轮扩散都在「占领」一圈新的海洋格子。最后一轮被占领的海洋格子，就是离陆地最远的那个。

为什么从所有陆地同时出发？
如果只从一个陆地出发去 BFS（广度优先搜索），得到的是离这个陆地最远的点，但不一定是离所有陆地都远的点。而「多源 BFS」就是从所有陆地同时开始扩散，每个海洋格子被最早到达它的那块陆地「占领」，这时候的距离就是它离最近陆地的距离。最后一个被占领的海洋格子，自然就是离所有陆地最远的那个了。

用人话来说，这就像在池塘里同时丢进好几块石头，每块石头都会产生一圈圈波纹。当所有波纹都覆盖了整个池塘时，最后一个被波纹覆盖到的地方，就是离所有石头最远的位置。

步骤拆解：

把所有陆地格子放进队列。 每个陆地格子就是一块「石头」，它们同时开始扩散。
检查特殊情况。 如果格子全是海洋（队列为空）或者全是陆地（队列里有全部格子），那就不存在「海洋到陆地的距离」，直接返回 $-1$ 。
一层层往外扩散。 每次从队列中取出一批格子，看它们的上下左右四个邻居：
- 如果邻居是海洋（ $0$ ），说明这块海洋第一次被陆地「接触到」，把它标记为已访问（改成 $1$ 避免重复处理），加入队列，距离加 $1$ 。
返回最终距离。 当队列为空时，最后一轮扩散的距离就是最大距离。

为什么这样能得到最远距离？ BFS 的特性就是从起点出发一层层往外走，每一层遍历完距离才加 1。最后一层遍历到的格子，就是最远的。

思路 1：代码

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n = len(grid)  # 网格的大小
        queue = deque()
        
        # 第 1 步：把所有陆地格子都加入队列，作为 BFS 的起点
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    queue.append((i, j))
        
        # 第 2 步：如果全是海洋或全是陆地，不存在有效距离，返回 -1
        if len(queue) == 0 or len(queue) == n * n:
            return -1
        
        # 四个移动方向：上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        distance = -1  # 记录当前扩散到了第几层
        
        # 第 3 步：多源 BFS，一层层往外扩散
        while queue:
            size = len(queue)  # 当前这一层有多少个格子
            for _ in range(size):
                x, y = queue.popleft()  # 取出当前位置
                
                # 向四个方向扩散
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    
                    # 检查新位置有没有超出边界，以及是不是海洋
                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                        grid[nx][ny] = 1   # 标记为已访问（变成陆地，不再重复处理）
                        queue.append((nx, ny))  # 下一轮扩散
            distance += 1  # 每扩散完一层，距离加 1
        
        # 第 4 步：返回最大距离
        return distance

思路 1：复杂度分析

时间复杂度： $O(n^2)$ 。用人话说就是：网格有多大，我们就遍历一遍，每个格子最多被访问一次。
空间复杂度： $O(n^2)$ 。队列里最多需要存整个网格的格子数量。