01 Matrix（01 矩阵）

题目 / Problem

中文： 给定一个 m × n 的二进制矩阵 mat，返回一个同样大小的矩阵，其中每个位置保存该单元格到最近的 0 的距离。

两个共享一条边的单元格之间距离为 1。因此只能向上、下、左、右移动，不能沿对角线移动。

English: Given an m × n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two cells sharing a common edge is 1. Movement is therefore allowed only up, down, left, and right, not diagonally.

示例 / Examples

Example 1

01 Matrix 示例一输入 / 01 Matrix example 1 input

Input:  mat = [[0,0,0],
               [0,1,0],
               [0,0,0]]

Output:       [[0,0,0],
               [0,1,0],
               [0,0,0]]

中心位置的 1 与四周任意一个 0 都只相隔一条边，所以距离为 1。
The center 1 is one edge away from each adjacent 0, so its distance is 1.

Example 2

01 Matrix 示例二输入 / 01 Matrix example 2 input

Input:  mat = [[0,0,0],
               [0,1,0],
               [1,1,1]]

Output:       [[0,0,0],
               [0,1,0],
               [1,2,1]]

最下方中间位置 (2,1) 到最近的 0 需要移动两步，例如 (2,1) → (1,1) → (0,1)，因此距离为 2。
The bottom-middle cell (2,1) needs two moves to reach the nearest 0, for example (2,1) → (1,1) → (0,1), so its distance is 2.

约束 / Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 10⁴
1 <= m × n <= 10⁴
mat[i][j] 为 0 或 1。
mat[i][j] is either 0 or 1.
mat 中至少存在一个 0。
There is at least one 0 in mat.

解题思路一：多源 BFS / Approach 1: Multi-Source BFS

如果从每个值为 1 的位置分别搜索最近的 0，会重复遍历大量单元格。更高效的方式是反向思考：
Searching separately from every 1 for its nearest 0 repeatedly visits many cells. Instead, reverse the perspective:

将所有值为 0 的位置同时作为 BFS 起点，逐层向外扩散。
Use every 0 cell as a BFS source and expand outward level by level.

所有 0 到自身的距离都是 0。多源 BFS 第一次到达某个 1 时，走过的步数一定是该位置到任意 0 的最短距离。
Every 0 has distance 0 from itself. The first time multi-source BFS reaches a 1, the number of steps taken is its shortest distance to any 0.

初始化 / Initialization

创建距离矩阵 distances，所有位置初始化为 -1，表示尚未访问。
Create distances and initialize every cell to -1, meaning unvisited.
遍历矩阵，将所有值为 0 的位置距离设为 0，并全部加入队列。
Scan the matrix, set every 0 cell's distance to 0, and enqueue all of them.

BFS 扩散 / BFS Expansion

每次从队列中取出 (row, col)，检查四个相邻位置。如果相邻位置合法且仍为 -1：
Dequeue (row, col) and inspect its four neighbors. If a neighbor is in bounds and still equals -1:

neighborDistance = distances[row][col] + 1

设置距离后立即加入队列。一个位置只会被首次到达并入队一次。
Set its distance and enqueue it immediately. Every cell is reached and enqueued only once.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
function updateMatrix(mat) {
  const rows = mat.length;
  const cols = mat[0].length;
  const distances = Array.from(
    { length: rows },
    () => new Array(cols).fill(-1),
  );
  const queue = [];
  let front = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (mat[row][col] === 0) {
        distances[row][col] = 0;
        queue.push([row, col]);
      }
    }
  }

  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  while (front < queue.length) {
    const [row, col] = queue[front++];

    for (const [rowOffset, colOffset] of directions) {
      const nextRow = row + rowOffset;
      const nextCol = col + colOffset;

      if (
        nextRow >= 0 &&
        nextRow < rows &&
        nextCol >= 0 &&
        nextCol < cols &&
        distances[nextRow][nextCol] === -1
      ) {
        distances[nextRow][nextCol] = distances[row][col] + 1;
        queue.push([nextRow, nextCol]);
      }
    }
  }

  return distances;
}

这里使用 front 索引读取队列，没有使用 JavaScript 数组的 shift()。shift() 可能在每次调用时移动剩余元素，导致额外开销。
The front index reads from the queue instead of using JavaScript's shift(), which may move the remaining elements on every call.

执行过程 / Walkthrough

以 Example 2 为例：
For Example 2:

第 0 层：所有 BFS 起点 / Level 0: All BFS Sources

0  0  0
0  ·  0
·  ·  ·

所有 0 同时进入队列，距离为 0。符号 · 表示尚未访问。
All 0 cells enter the queue with distance 0. The symbol · means unvisited.

第 1 层：与任意 0 相邻的位置 / Level 1: Adjacent to Any Zero

0  0  0
0  1  0
1  ·  1

这些位置第一次从某个 0 到达，所以距离为 1。
These cells are first reached from a 0, so their distance is 1.

第 2 层：剩余位置 / Level 2: Remaining Cell

0  0  0
0  1  0
1  2  1

最下方中间位置从距离为 1 的位置扩散得到，因此距离为 2。
The bottom-middle cell is reached from a cell at distance 1, so its distance is 2.

为什么第一次到达就是最短距离？ / Why Is the First Visit the Shortest?

BFS 按距离从小到大逐层访问节点。多源 BFS 等价于创建一个虚拟起点，并让它以距离 0 连接所有原始 0。
BFS visits nodes level by level in nondecreasing distance order. Multi-source BFS is equivalent to adding a virtual source connected at distance 0 to every original 0.

因此，一个位置第一次被访问时，所有更短的可能路径都已经被处理；它不可能在之后找到更短的距离。
Therefore, when a cell is first visited, every possible shorter path has already been considered, and no later path can improve its distance.

BFS 复杂度 / BFS Complexity

设矩阵共有 m × n 个单元格。
Let the matrix contain m × n cells.

时间复杂度：O(mn)，每个单元格最多入队和出队一次。
Time: O(mn), because every cell is enqueued and dequeued at most once.
空间复杂度：O(mn)，距离矩阵和队列最多保存所有单元格。
Space: O(mn), because the distance matrix and queue may contain all cells.

解题思路二：两遍动态规划 / Approach 2: Two-Pass Dynamic Programming

一个位置到最近 0 的路径可能从四个方向到达。可以使用两次扫描分别覆盖这些方向：
A shortest path to a 0 may arrive from any of four directions. Two scans can cover all directions:

从左上到右下扫描，利用上方和左方的结果。
Scan from top-left to bottom-right, using top and left neighbors.
从右下到左上扫描，利用下方和右方的结果。
Scan from bottom-right to top-left, using bottom and right neighbors.

function updateMatrixDP(mat) {
  const rows = mat.length;
  const cols = mat[0].length;
  const maxDistance = rows + cols;
  const distances = Array.from(
    { length: rows },
    () => new Array(cols).fill(maxDistance),
  );

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (mat[row][col] === 0) {
        distances[row][col] = 0;
        continue;
      }

      if (row > 0) {
        distances[row][col] = Math.min(
          distances[row][col],
          distances[row - 1][col] + 1,
        );
      }

      if (col > 0) {
        distances[row][col] = Math.min(
          distances[row][col],
          distances[row][col - 1] + 1,
        );
      }
    }
  }

  for (let row = rows - 1; row >= 0; row--) {
    for (let col = cols - 1; col >= 0; col--) {
      if (row < rows - 1) {
        distances[row][col] = Math.min(
          distances[row][col],
          distances[row + 1][col] + 1,
        );
      }

      if (col < cols - 1) {
        distances[row][col] = Math.min(
          distances[row][col],
          distances[row][col + 1] + 1,
        );
      }
    }
  }

  return distances;
}

初始大值使用 rows + cols 即可，因为矩阵内任意两点之间的曼哈顿距离不会达到该值。
rows + cols is a sufficient initial upper bound because the Manhattan distance between any two matrix cells is smaller than this value.

时间复杂度 / Time: O(mn)
空间复杂度 / Space: O(mn)，用于返回距离矩阵。
The returned distance matrix uses O(mn) space.

BFS 与动态规划对比 / BFS vs. Dynamic Programming

方法 / Method	时间 / Time	空间 / Space	核心思想 / Key Idea
多源 BFS	`O(mn)`	`O(mn)`	从所有 `0` 同时逐层扩散 / Expand from all zeros simultaneously
两遍 DP	`O(mn)`	`O(mn)`	两种扫描方向覆盖四个邻居 / Two scan directions cover four neighbors

多源 BFS 的最短路含义更直接，也更容易推广到带障碍物或不规则图结构。
Multi-source BFS has a more direct shortest-path interpretation and generalizes more naturally to obstacles or irregular graph structures.

与 Map of Highest Peak 的关系 / Relation to Map of Highest Peak

本题与 LeetCode 1765 Map of Highest Peak 使用相同的多源 BFS 框架：将所有特殊位置作为距离或高度为 0 的起点，再逐层向外扩散。
This problem and LeetCode 1765, Map of Highest Peak, use the same multi-source BFS framework: initialize all special cells at distance or height 0, then expand outward level by level.

易错点 / Common Pitfalls

必须将所有 0 同时加入初始队列，而不是只选择一个 0。
Enqueue every 0 initially, not just one of them.
只能向上、下、左、右移动，不能计算对角线距离。
Move only up, down, left, and right; diagonals do not count.
应在位置加入队列时立即标记距离，避免它被重复入队。
Assign a distance when enqueuing a cell to prevent duplicate enqueue operations.
不要从每个 1 分别运行一次 BFS，否则最坏时间复杂度会非常高。
Do not run a separate BFS from every 1, which can be prohibitively expensive.
使用 -1 区分“未访问”和合法距离 0。
Use -1 to distinguish unvisited cells from the valid distance 0.
两遍 DP 的扫描方向必须相反，才能覆盖来自四个方向的最短路径。
The two DP scans must use opposite directions to account for shortest paths arriving from all four sides.

01 Matrix