LeetCode 542. 01 矩阵

题目描述
给定一个由 0 和 1 组成的矩阵 mat，找出每个元素到最近的 0 的距离。返回一个距离矩阵，其中每个元素表示该位置到最近的 0 的曼哈顿距离（即只能上下左右移动，且距离为步数）。矩阵的大小不超过 \(10^4 \times 10^4\)。

示例
输入：

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

输出：

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

解题思路

关键观察

1. 多源最短路径问题：每个 1 需要找到最近的 0，可视为多个起点（所有 0）同时向外扩散的 BFS。
2. 动态规划（DP）思路：最近距离可能来自上下左右四个方向，可分两轮扫描：
   • 第一轮从左上到右下，考虑 左上方向 的最短距离。
   • 第二轮从右下到左上，考虑 右下方向 的最短距离，结合第一轮结果。

方法一：多源 BFS

步骤

1. 将所有 0 的位置加入队列，距离设为 0；将 1 的位置初始化为一个极大值（如 INT_MAX）。
2. 从队列中取出位置 (r, c)，检查其上下左右四个邻居：
   • 若邻居的距离可更新（即当前距离 +1 小于邻居的当前值），则更新邻居的距离，并将其加入队列。
3. 重复直到队列为空。

为什么可行

• BFS 保证每次扩散一步，所有 0 同时作为起点，首次遇到某个 1 时即为最短距离。

复杂度

• 时间复杂度：\(O(m \times n)\)，每个节点入队一次。
• 空间复杂度：\(O(m \times n)\)，队列和距离矩阵的开销。

方法二：动态规划（两次扫描）

步骤

1. 初始化距离矩阵 dist，其中 0 的位置为 0，1 的位置为 INT_MAX。
2. 第一轮（左上→右下）：
   • 遍历每个位置 (i, j)，若该位置不为 0，则检查 左方和上方 邻居，更新：

\[ dist[i][j] = \min(dist[i][j], dist[i-1][j] + 1, dist[i][j-1] + 1) \]

 （注意边界判断）  

3. 第二轮（右下→左上）：
   • 遍历每个位置 (i, j)，若该位置不为 0，则检查 右方和下方 邻居，更新：

\[ dist[i][j] = \min(dist[i][j], dist[i+1][j] + 1, dist[i][j+1] + 1) \]

4. 返回 dist 矩阵。

为什么可行

• 最短路径可能来自四个方向，但两次扫描可覆盖所有方向：
  • 第一轮保证左上方向的最优解。
  • 第二轮保证右下方向的最优解，结合后即为全局最优。

复杂度

• 时间复杂度：\(O(m \times n)\)，两次线性扫描。
• 空间复杂度：\(O(m \times n)\)，存储距离矩阵（若允许修改输入矩阵可降至 \(O(1)\)）。

举例说明（DP 方法）

输入矩阵：

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

第一轮（左上→右下）

• 初始 dist：

  [0,0,0]
  [0,∞,0]
  [∞,∞,∞]
  

• 扫描到 (1,1)（值为 1）：比较左和上，取 min(∞, 0+1, 0+1)=1，更新为 1。
• 扫描到 (2,0)：只有上方 (1,0)=0，更新为 1。
• 扫描到 (2,1)：比较左 (2,0)=1 和上 (1,1)=1，取 1+1=2。
• 扫描到 (2,2)：比较左 (2,1)=2 和上 (1,2)=0，取 0+1=1。
• 第一轮后：

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

第二轮（右下→左上）

• 从 (2,2) 开始：比较右和下（越界），不变。
• (2,1)：比较右 (2,2)=1 和下（越界），取 min(2, 1+1)=2，但 2 不变。
• (2,0)：比较右 (2,1)=2，取 min(1, 2+1)=1，不变。
• (1,2)：比较右（越界）和下 (2,2)=1，取 min(0, 1+1)=0，不变。
• (1,1)：比较右 (1,2)=0 和下 (2,1)=2，取 min(1, 0+1, 2+1)=1，不变。
• 最终结果与第一轮相同，即为答案。

总结

• BFS 方法 直观符合扩散过程，适合理解。
• DP 方法 无需队列，性能更优，但需要理解两次扫描的覆盖性。
• 关键点：将多源最短路径转化为单源动态规划，通过方向分解降低复杂度。