Rotting Oranges（腐烂的橘子）

题目 / Problem

中文： 给定一个 m × n 的网格 grid，每个单元格可能包含以下三种值之一：

0：空单元格。
An empty cell.
1：新鲜橘子。
A fresh orange.
2：腐烂橘子。
A rotten orange.

每过一分钟，所有与腐烂橘子在上、下、左、右四个方向相邻的新鲜橘子都会腐烂。

返回直到网格中不再有新鲜橘子所需的最少分钟数。如果无法让所有新鲜橘子腐烂，返回 -1。

English: You are given an m × n grid where 0 represents an empty cell, 1 a fresh orange, and 2 a rotten orange.

Every minute, each fresh orange that is four-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes until no fresh orange remains. If this is impossible, return -1.

示例 / Examples

Example 1

腐烂橘子从第 0 分钟到第 4 分钟的扩散过程 / Rotting oranges spreading from minute 0 through minute 4

Input:  grid = [[2,1,1],
                [1,1,0],
                [0,1,1]]

Output: 4

腐烂从左上角开始逐层扩散，经过 4 分钟后所有新鲜橘子都腐烂。
Rot spreads outward from the top-left corner, and every fresh orange is rotten after 4 minutes.

Example 2

Input:  grid = [[2,1,1],
                [0,1,1],
                [1,0,1]]

Output: -1

左下角位置 (2,0) 被空单元格阻隔，无法通过四方向路径接触到任何腐烂橘子，因此返回 -1。
The bottom-left orange at (2,0) is isolated by empty cells and cannot be reached through a four-directional path, so return -1.

Example 3

Input:  grid = [[0,2]]
Output: 0

第 0 分钟时已经没有新鲜橘子，因此无需等待。
There are no fresh oranges at minute 0, so no waiting is needed.

约束 / Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 为 0、1 或 2。
grid[i][j] is 0, 1, or 2.

核心思想：多源 BFS / Key Idea: Multi-Source BFS

腐烂过程是从所有初始腐烂橘子同时开始的。如果只从一个腐烂橘子搜索，无法正确模拟同一分钟内多处同时扩散。
Rotting begins simultaneously from every initially rotten orange. Starting from only one source would fail to model concurrent spreading.

因此：
Therefore:

将所有初始腐烂橘子同时加入队列。
Enqueue all initially rotten oranges.
统计初始新鲜橘子的数量 fresh。
Count the initial fresh oranges in fresh.
使用 BFS 逐层处理。队列中的每一层表示同一分钟内能够传播腐烂的橘子。
Run BFS level by level; each queue level represents oranges spreading rot during the same minute.
每感染一个新鲜橘子，就将它改为 2、加入队列，并将 fresh 减 1。
Whenever a fresh orange is infected, change it to 2, enqueue it, and decrement fresh.
BFS 结束后，如果 fresh === 0，返回经过的分钟数；否则返回 -1。
After BFS, return elapsed minutes if fresh === 0; otherwise return -1.

多源 BFS 从所有起点按距离逐层扩散，所以某个新鲜橘子第一次被访问时，就是它能够腐烂的最早分钟。
Multi-source BFS expands from all sources in distance order, so the first visit to a fresh orange occurs at its earliest possible rotting minute.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[][]} grid
 * @return {number}
 */
function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const queue = [];
  let front = 0;
  let fresh = 0;

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === 2) {
        queue.push([row, col]);
      } else if (grid[row][col] === 1) {
        fresh++;
      }
    }
  }

  if (fresh === 0) {
    return 0;
  }

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

  while (front < queue.length && fresh > 0) {
    const levelSize = queue.length - front;

    for (let i = 0; i < levelSize; i++) {
      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 &&
          grid[nextRow][nextCol] === 1
        ) {
          grid[nextRow][nextCol] = 2;
          fresh--;
          queue.push([nextRow, nextCol]);
        }
      }
    }

    minutes++;
  }

  return fresh === 0 ? minutes : -1;
}

这里使用 front 索引读取队列，避免调用 JavaScript 数组的 shift()。
An index named front reads from the queue instead of using JavaScript's shift().

该实现会将被感染的位置从 1 改为 2，因此会修改输入网格。
This implementation changes infected cells from 1 to 2, so it mutates the input grid.

执行过程 / Walkthrough

以 Example 1 为例，R 表示腐烂橘子，F 表示新鲜橘子，· 表示空单元格：
For Example 1, let R represent rotten, F fresh, and · empty:

第 0 分钟 / Minute 0

R F F
F F ·
· F F

初始腐烂橘子 (0,0) 入队，新鲜橘子数量为 6。
The initial rotten orange (0,0) is enqueued, and fresh = 6.

第 1 分钟 / Minute 1

R R F
R F ·
· F F

位置 (0,1) 和 (1,0) 腐烂，fresh = 4。
Cells (0,1) and (1,0) rot, leaving fresh = 4.

第 2 分钟 / Minute 2

R R R
R R ·
· F F

位置 (0,2) 和 (1,1) 腐烂，fresh = 2。
Cells (0,2) and (1,1) rot, leaving fresh = 2.

第 3 分钟 / Minute 3

R R R
R R ·
· R F

位置 (2,1) 腐烂，fresh = 1。
Cell (2,1) rots, leaving fresh = 1.

第 4 分钟 / Minute 4

R R R
R R ·
· R R

位置 (2,2) 腐烂，fresh = 0，因此返回 4。
Cell (2,2) rots, making fresh = 0, so return 4.

为什么按层增加分钟？ / Why Increment Minutes by Level?

在某一分钟开始时，队列中已有的节点可以同时感染相邻橘子。它们新感染的橘子要到下一分钟才能继续传播。
At the start of a minute, every node already in the queue can infect adjacent oranges simultaneously. Newly infected oranges can spread only during the next minute.

因此每轮开始时先固定：
At the start of each round, capture:

const levelSize = queue.length - front;

只处理当前的 levelSize 个节点，完成后再将 minutes 加 1。这样新加入的节点不会被误算到同一分钟。
Process exactly these levelSize nodes, then increment minutes. This prevents newly enqueued oranges from spreading in the same minute.

为什么先检查 `fresh === 0`？ / Why Check `fresh === 0` First?

如果开始时没有新鲜橘子，答案必须是 0。如果直接进入按层 BFS 并无条件增加分钟，可能错误地把已有腐烂橘子的处理算成一分钟。
If there are no fresh oranges initially, the answer must be 0. Entering level-order BFS and incrementing minutes unconditionally could incorrectly count processing existing rotten oranges as one minute.

提前返回也正确处理了只有空格子、只有腐烂橘子等情况。
The early return also handles grids containing only empty cells or only rotten oranges.

无法完成的情况 / Impossible Case

Example 2 中的 (2,0) 四个方向要么越界，要么是空单元格：
In Example 2, all four directions from (2,0) are either outside the grid or empty:

R F F
· F F
F · F
↑
永远无法到达 / Never reachable

BFS 队列最终耗尽，但 fresh > 0，所以返回 -1。
The BFS queue eventually empties while fresh > 0, so return -1.

复杂度 / Complexity

设网格大小为 m × n。
Let the grid size be m × n.

时间复杂度：O(mn)，每个单元格最多扫描一次，每个橘子最多入队一次。
Time: O(mn), because each cell is scanned once and each orange is enqueued at most once.
空间复杂度：O(mn)，最坏情况下队列可能保存大量橘子位置。
Space: O(mn), because the queue may hold many orange positions.

与普通单源 BFS 的区别 / Difference from Single-Source BFS

普通 BFS 从一个起点计算到其他位置的最短距离。本题有多个初始腐烂橘子，它们在第 0 分钟同时开始传播，因此必须全部作为 BFS 起点。
Ordinary BFS computes distances from one source. Here, multiple initially rotten oranges begin spreading at minute 0, so all must serve as BFS sources.

这与“01 Matrix”中将所有 0 同时入队的思路相同：都在计算每个位置到最近起点的最短距离。
This matches the approach used in “01 Matrix,” where all zeros are enqueued together: both compute shortest distance to the nearest source.

易错点 / Common Pitfalls

必须将所有初始腐烂橘子同时加入队列。
Enqueue all initially rotten oranges together.
只考虑上、下、左、右四个方向，不能沿对角线传播。
Spread only in four directions, never diagonally.
新鲜橘子加入队列时就要改为 2，防止被重复感染和入队。
Change a fresh orange to 2 when enqueuing it to prevent duplicate infection and enqueue operations.
每一层 BFS 对应一分钟，必须先固定 levelSize。
Each BFS level represents one minute, so capture levelSize first.
初始时没有新鲜橘子应返回 0，不是 -1。
Return 0, not -1, when there are no fresh oranges initially.
BFS 结束后仍有新鲜橘子才返回 -1。
Return -1 only if fresh oranges remain after BFS.
不要在每处理一个橘子时增加分钟，分钟应按整层增加。
Do not increment minutes per orange; increment once per complete level.

Rotting Oranges