994.

腐烂的橘子

中等

在给定的m

n网格grid中，每个单元格可以有以下三个值之一：

• 值0代表空单元格；
• 值1代表新鲜橘子；
• 值2代表腐烂的橘子。

每分钟，腐烂的橘子周围

个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。

如果不可能，返回-1。

示例

/>

输入：grid
=
输出：4

示例

2：

输入：grid
=
列）永远不会腐烂，因为腐烂只会发生在
个方向上。

示例

3：

输入：grid
=
。

提示：

• m

  ==

  grid.length

• n

  ==

  grid[i].length

• 1

  <=

  10

• grid[i][j]仅为0、1或2

📝

(Rotting

(一句话总结)

“丧尸围城：所有源头同时爆发，一圈一圈向外感染。

”这不是从一个点开始搜，而是从所有一开始就腐烂的橘子同时开始扩散。

💡图像记忆

(水波纹)：

• 往湖里扔这几颗石头（腐烂橘子）。

• 波纹（感染范围）同时向外扩散。

• 问波纹覆盖所有水面（新鲜橘子）需要几秒。

2.

算法流程

(Init)：

• • 扫描全图。

  • 统计fresh(新鲜橘子数量)

    ->

    用于最后判断是否成功。

  • 将所有初始的2(腐烂橘子)

    加入队列

    ->多源起点。

1. 一分钟一圈

   (BFS

   Loop)：

• • 只要还有fresh且

    队列不空：

  • 时间

    +

    1。

  • 快照当前队列：把当前这一轮的所有坏橘子拿出来，感染它们的上下左右。

  • 新感染入队：被染红的橘子，变成下一轮的传染源。

1. 大结局

   (Result)：

• • 如果fresh

    ==

    0，返回时间。

  • 如果fresh

    >

    0(还有幸存者，但队列空了)，说明有孤岛，返回-1。

🔍

代码回忆清单

(一句话总结)

“生化危机模式：所有传染源同时向外爆发，利用‘双列表’交替模拟时间的流逝。

”

• 多源

  BFS：这不是从单一节点出发的搜索，而是将所有初始烂橘子视为“第

  层”，它们在同一时刻向外扩散。

• 层序遍历优化：您使用了List替换法

  (tmp和q交替)

  来代替传统的队列size循环，这在

  Java

  中处理分层逻辑时非常清晰。

• 精准计时：利用fresh

  >

  (Init)：

• • 扫描全图。

  • 统计新鲜橘子数量fresh。

  • 将所有烂橘子2加入列表q(作为第

    层)。

1. 按分钟循环

   (Loop)：

• • 条件：while

    (fresh

    !q.isEmpty())。

    只有当“还有人没被感染”且“还有传染源”时，时间才流动。

  • 计时：ans++。

  • 交替：保存当前层tmp

    =

    ArrayList()。

1. 扩散

   (Spread)：

• • 遍历tmp中的每个坐标。

  • 检查四周邻居。

    如果是新鲜橘子1：

• • • fresh--(幸存者减少)。

    • grid[i][j]

      =

      2(标记腐烂，防止重复)。

    • 加入下一层q。

1. 结算

   (Result)：循环结束后，如果fresh仍大于

   -1；否则返回ans。

🔍

题目：LC

初始化：全图扫描，区分传染源和幸存者

for

结算：还有幸存者说明被墙隔绝了，返回

return

]为什么循环条件必须加fresh

>

0？

• • 如果不加，当最后一批橘子被感染并加入q后，while

    (!q.isEmpty())会再次进入循环。

  • 虽然这一轮不会感染新橘子，但ans会无故++。

    加了fresh

    >

    0后，一旦没有幸存者，立即停止计时，结果精准。

• [

  ]List

  传统写法？

• • List

    =

    new...。

    逻辑是“处理完这一整批，再生成下一批”。

    内存上有些微

    开销，但逻辑清晰，不易出错。

  • Queue

    size

    0)...。

    这是教科书写法，内存复用更好。

  • 结论：面试中两者皆可，您的写法在

    Java

    中由于ArrayList的高效性，性能通常很好。

• [

  ]边界条件

  check

• • 如果一开始fresh

    ==

    0？循环直接不执行，返回ans

    (0)。

    正确。

  • 如果一开始没有烂橘子但有新鲜橘子？循环不执行，返回fresh

    >

    -1。

    正确。

🖼️

1],

1]]

1. Init:fresh

   =

   [(0,0)].

2. Loop

   1:

• • Check:fresh(6)

    >

    1.

  • Spread:(0,0)感染(0,1)和(1,0).
  • Update:fresh

    =

    4,q变为[(0,1),

    (1,0)].

1. Loop

   2:

• • Check:fresh(4)

    >

    2.

  • Spread:(0,1)感染(0,2)和(1,1).(1,0)的邻居(1,1)已经是

    了(刚变的)，跳过。

  • Update:fresh

    =

    2,q变为[(0,2),

    (1,1)].

1. Loop

   3:

• • Check:fresh(2)

    >

    3.

  • Spread:(1,1)感染(2,1).
  • Update:fresh

    =

    1,q变为[(2,1)].

1. Loop

   4:

• • Check:fresh(1)

    >

    4.

  • Spread:(2,1)感染(2,2).
  • Update:fresh

    =

    0,q变为[(2,2)].

1. Loop

   5:

• • Check:fresh(0)

    >

    0isFalse.

    Stop.

1. Result:

   ---