LeetCode 542. 01 矩阵

题目描述
给定一个由 0 和 1 组成的矩阵 mat，矩阵的行数和列数均为正整数。要求返回一个同样大小的矩阵，其中每个元素是原始矩阵中对应位置到最近的 0 的距离。相邻单元格指的是上、下、左、右四个方向。两个相邻单元格间的距离为 1。

示例
输入：

mat = [[0,0,0],
       [0,1,0],
       [0,0,0]]

输出：

[[0,0,0],
 [0,1,0],
 [0,0,0]]

解释：中心的 1 自身就是 0 的邻居，距离为 1，但结果中 1 表示距离 0 为 1 的距离（通常输入中 1 表示障碍或非零，输出中 1 表示距离）。

限制条件

• 矩阵大小至少为 1×1，最大可达 10^4 个单元格。
• 矩阵中至少有一个 0。

解题思路
本题可以理解为：对于矩阵中的每个 1，找到它到最近的 0 的最短距离。由于是四个方向等权移动，典型的思路是多源广度优先搜索（BFS） 或动态规划。这里我们使用多源 BFS 来讲解，因为它更直观且易于理解。

核心思想：

1. 将所有 0 的位置作为 BFS 的起点（初始层），因为 0 到自身的距离是 0。
2. 从这些起点同时开始 BFS，逐层向外扩展，每次扩展距离增加 1。
3. 当遇到 1 时，记录当前距离，并将这个 1 的位置加入队列，以便继续向外扩展（避免重复访问）。
4. 最终得到每个位置到最近 0 的距离。

详细步骤

步骤 1：初始化

• 获取矩阵的行数 m 和列数 n。
• 创建一个和原始矩阵相同大小的结果矩阵 dist，初始值设为 -1 表示未访问。
• 创建一个队列 queue（通常用双端队列），用于 BFS。

步骤 2：多源起点入队

• 遍历整个矩阵，对于每个位置 (r, c)：
  • 如果 mat[r][c] == 0，说明这个位置自身就是 0，距离为 0。
    • 将 dist[r][c] 设为 0。
    • 将该位置 (r, c) 加入队列，作为 BFS 的起点。
  • 如果 mat[r][c] == 1，说明是待计算距离的点，暂时不处理。

步骤 3：BFS 扩展

• 当队列不为空时，取出队首位置 (r, c)。
• 检查其上、下、左、右四个邻居 (nr, nc)：
  • 确保邻居在矩阵范围内。
  • 如果 dist[nr][nc] == -1（即未访问过，一定是 1 的位置，因为 0 的位置初始时已标记距离 0 并已入队过，不会再访问到）：
    • 这个邻居到最近 0 的距离 = dist[r][c] + 1。
    • 将 dist[nr][nc] 设为该距离。
    • 将邻居 (nr, nc) 加入队列，以便继续向外扩展。

步骤 4：返回结果

• BFS 结束后，dist 矩阵即为所求。

为什么这样做是正确的？

• 因为 BFS 从所有 0 同时开始，第一次遇到某个 1 时，经过的层数（距离）就是最短距离（BFS 保证最短路径）。
• 每个 1 只会被访问一次，时间复杂度 O(m×n)。

示例推演
以示例矩阵为例：

mat = [[0,0,0],
       [0,1,0],
       [0,0,0]]

1. 初始：所有 0 的位置入队，dist 中对应位置设为 0。
2. 从队列中取出 (0,0)，检查邻居，没有未访问的 1。
3. 不断处理队列中的 0，直到遇到 (1,1) 的邻居。比如从 (1,0) 扩展时，邻居 (1,1) 是 1 且未访问，则 dist[1][1] = dist[1][0] + 1 = 1，并将 (1,1) 入队。
4. 最终 dist 矩阵中所有 1 都变为 1（表示距离），所有 0 仍为 0。

输出：

[[0,0,0],
 [0,1,0],
 [0,0,0]]

注意：输出中的 1 是距离值，不是原始矩阵的 1。

复杂度分析

• 时间复杂度：O(m×n)，每个单元格最多入队一次。
• 空间复杂度：O(m×n)，用于队列和结果矩阵。

这种方法直观高效，是解决此类“多源最短路径”问题的经典方案。