994. 腐烂的橘子

994. 腐烂的橘子

中等

在给定的m x n网格grid中，每个单元格可以有以下三个值之一：

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

每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回-1。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]] 输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]] 输出：-1 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

输入：grid = [[0,2]] 输出：0 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j]仅为0、1或2

📝 核心笔记：腐烂的橘子 (Rotting Oranges)

1. 核心思想 (一句话总结)

“丧尸围城：所有源头同时爆发，一圈一圈向外感染。”这不是从一个点开始搜，而是从所有一开始就腐烂的橘子同时开始扩散。💡图像记忆 (水波纹)：

• 往湖里扔这几颗石头（腐烂橘子）。
• 波纹（感染范围）同时向外扩散。
• 问波纹覆盖所有水面（新鲜橘子）需要几秒。

2. 算法流程 (三步走)

1. 全员集结 (Init)：

• • 扫描全图。
  • 统计fresh(新鲜橘子数量) -> 用于最后判断是否成功。
  • 将所有初始的2(腐烂橘子) 加入队列 ->多源起点。

1. 一分钟一圈 (BFS Loop)：

• • 只要还有fresh且 队列不空：
  • 时间 + 1。
  • 快照当前队列：把当前这一轮的所有坏橘子拿出来，感染它们的上下左右。
  • 新感染入队：被染红的橘子，变成下一轮的传染源。

1. 大结局 (Result)：

• • 如果fresh == 0，返回时间。
  • 如果fresh > 0(还有幸存者，但队列空了)，说明有孤岛，返回-1。

🔍 代码回忆清单 (带注释版)

📝 核心笔记：腐烂的橘子 (Rotting Oranges)

1. 核心思想 (一句话总结)

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

• 多源 BFS：这不是从单一节点出发的搜索，而是将所有初始烂橘子视为“第 0 层”，它们在同一时刻向外扩散。
• 层序遍历优化：您使用了List替换法 (tmp和q交替) 来代替传统的队列size循环，这在 Java 中处理分层逻辑时非常清晰。
• 精准计时：利用fresh > 0作为循环护栏，完美解决了标准 BFS 容易“多算一分钟”的痛点。

2. 算法流程 (BFS 分层)

1. 初始化 (Init)：

• • 扫描全图。
  • 统计新鲜橘子数量fresh。
  • 将所有烂橘子2加入列表q(作为第 0 层)。

1. 按分钟循环 (Loop)：

• • 条件：while (fresh > 0 && !q.isEmpty())。只有当“还有人没被感染”且“还有传染源”时，时间才流动。
  • 计时：ans++。
  • 交替：保存当前层tmp = q，重置下一层q = new ArrayList()。

1. 扩散 (Spread)：

• • 遍历tmp中的每个坐标。
  • 检查四周邻居。如果是新鲜橘子1：

• • • fresh--(幸存者减少)。
    • grid[i][j] = 2(标记腐烂，防止重复)。
    • 加入下一层q。

1. 结算 (Result)：循环结束后，如果fresh仍大于 0，说明有橘子不可达，返回 -1；否则返回ans。

🔍 代码回忆清单

// 题目：LC 994. Rotting Oranges class Solution { private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向 public int orangesRotting(int[][] grid) { int m = grid.length; int n = grid[0].length; int fresh = 0; List<int[]> q = new ArrayList<>(); // 1. 初始化：全图扫描，区分传染源和幸存者 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { fresh++; // 统计新鲜橘子个数 } else if (grid[i][j] == 2) { q.add(new int[]{i, j}); // 一开始就腐烂的橘子 } } } int ans = 0; // 2. 核心循环：多源 BFS // 亮点：fresh > 0 这个条件非常关键，它避免了最后一轮空转导致 ans 多加 1 while (fresh > 0 && !q.isEmpty()) { ans++; // 经过一分钟 List<int[]> tmp = q; // 当前这一分钟要处理的烂橘子 q = new ArrayList<>(); // 准备下一分钟被感染的烂橘子 for (int[] pos : tmp) { for (int[] d : DIRECTIONS) { int i = pos[0] + d[0]; int j = pos[1] + d[1]; // 3. 感染逻辑：只感染新鲜的(1) if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { fresh--; grid[i][j] = 2; // 状态置为腐烂，相当于 visited 标记 q.add(new int[]{i, j}); } } } } // 4. 结算：还有幸存者说明被墙隔绝了，返回 -1 return fresh > 0 ? -1 : ans; } }

⚡ 快速复习 CheckList (易错点)

• [ ]为什么循环条件必须加fresh > 0？

• • 如果不加，当最后一批橘子被感染并加入q后，while (!q.isEmpty())会再次进入循环。
  • 虽然这一轮不会感染新橘子，但ans会无故++。加了fresh > 0后，一旦没有幸存者，立即停止计时，结果精准。

• [ ]List 替换法 vs Queue 传统写法？

• • List 替换：tmp = q; q = new...。逻辑是“处理完这一整批，再生成下一批”。内存上有些微 GC 开销，但逻辑清晰，不易出错。
  • Queue 写法：int size = q.size(); while(size-- > 0)...。这是教科书写法，内存复用更好。
  • 结论：面试中两者皆可，您的写法在 Java 中由于ArrayList的高效性，性能通常很好。

• [ ]边界条件 check

• • 如果一开始fresh == 0？循环直接不执行，返回ans (0)。正确。
  • 如果一开始没有烂橘子但有新鲜橘子？循环不执行，返回fresh > 0 ? -1。正确。

🖼️ 数字演练

Grid:[[2, 1, 1], [1, 1, 0], [0, 1, 1]]

1. Init:fresh = 6,q = [(0,0)].
2. Loop 1:

• • Check:fresh(6) > 0. Enter.ans = 1.
  • Spread:(0,0)感染(0,1)和(1,0).
  • Update:fresh = 4,q变为[(0,1), (1,0)].

1. Loop 2:

• • Check:fresh(4) > 0. Enter.ans = 2.
  • Spread:(0,1)感染(0,2)和(1,1).(1,0)的邻居(1,1)已经是 2 了(刚变的)，跳过。
  • Update:fresh = 2,q变为[(0,2), (1,1)].

1. Loop 3:

• • Check:fresh(2) > 0. Enter.ans = 3.
  • Spread:(1,1)感染(2,1).
  • Update:fresh = 1,q变为[(2,1)].

1. Loop 4:

• • Check:fresh(1) > 0. Enter.ans = 4.
  • Spread:(2,1)感染(2,2).
  • Update:fresh = 0,q变为[(2,2)].

1. Loop 5:

• • Check:fresh(0) > 0isFalse. Stop.

1. Result: 4.