题目描述
给定一个m x n的网格grid，每个单元格可能有三种值：
0表示空单元格。1表示新鲜橘子。2表示腐烂的橘子。
每分钟，腐烂的橘子会让上下左右四个方向相邻的新鲜橘子腐烂。
要求返回直到没有新鲜橘子为止所需的最小分钟数。如果存在新鲜橘子永远无法腐烂，返回-1。
初始思路
一开始容易想到 DFS：从每个腐烂橘子出发，去感染周围的新鲜橘子。
但这个思路有一个关键问题：题目里的腐烂过程是“每分钟同时扩散”，而普通 DFS 更像是一条路径一直往深处走。DFS 不能自然表达“第 1 分钟腐烂哪些橘子，第 2 分钟腐烂哪些橘子”。
比如最开始写成“遇到腐烂橘子，就把周围一圈新鲜橘子变腐烂”，这其实只模拟了 1 分钟，并没有继续分层扩散，也没有正确统计答案。
所以这题更适合使用多源 BFS。
解题思路
把网格看成一张图：
- 每个橘子格子可以看作一个节点。
- 上下左右相邻表示节点之间有边。
- 所有初始腐烂橘子
2都是 BFS 的起点。
因为一开始可能有多个腐烂橘子，而且它们会同时向外扩散，所以不能只从一个点开始 BFS，而是要把所有初始腐烂橘子一起加入队列。这就是多源 BFS。
具体流程：
- 遍历整个
grid。 - 遇到腐烂橘子
2，加入队列。 - 遇到新鲜橘子
1，统计数量fresh++。 - BFS 每次处理当前队列中的
size个橘子。 - 这一批橘子代表同一分钟内会继续扩散的腐烂橘子。
- 如果感染到新鲜橘子，就把它改成
2，同时fresh--，再加入队列。 - BFS 结束后，如果
fresh == 0，说明所有新鲜橘子都腐烂了；否则返回-1。
为什么要按层 BFS
BFS 中的“一层”正好对应题目中的“一分钟”。
例如：
2 1 1 1 1 0 0 1 1第 1 分钟，初始腐烂橘子影响周围：
2 2 1 2 1 0 0 1 1第 2 分钟，新腐烂的橘子继续扩散：
2 2 2 2 2 0 0 1 1所以代码里需要先记录当前队列大小：
int size = queue.size();然后只处理这size个元素。新加入队列的橘子不能在同一分钟继续扩散，而是留到下一轮处理。
易错点
1. Java 数组入队写法
Java 中不能这样写：
queue.add({i, j});应该写成：
queue.add(new int[]{i, j});因为{i, j}只能在数组初始化语境中使用，不能单独作为一个对象传入方法。
2. BFS 循环条件
如果写成：
while (!queue.isEmpty()) { minutes++; }答案可能会多 1。
原因是最后一批刚刚腐烂的橘子还会留在队列里，再被处理一轮。但这一轮已经没有新的新鲜橘子可以腐烂了，不应该再增加分钟数。
更稳妥的写法是：
while (!queue.isEmpty() && fresh > 0) { minutes++; }只有在还存在新鲜橘子时，继续按分钟扩散。
3. 最后要判断是否还有新鲜橘子
BFS 结束不代表所有新鲜橘子都腐烂了。
如果某些新鲜橘子被空格隔开，永远无法被腐烂橘子感染，就需要返回-1。
所以最后要根据fresh判断：
return fresh == 0 ? minutes : -1;代码实现
class Solution { int[][] D = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } }; int m; int n; public int orangesRotting(int[][] grid) { m = grid.length; n = grid[0].length; Deque<int[]> queue = new ArrayDeque<>(); int fresh = 0; int minutes = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) { queue.add(new int[]{i, j}); } else if (grid[i][j] == 1) { fresh++; } } } while (!queue.isEmpty() && fresh > 0) { int size = queue.size(); minutes++; for (int i = 0; i < size; i++) { int[] cur = queue.poll(); for (int[] d : D) { int x = cur[0] + d[0]; int y = cur[1] + d[1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { grid[x][y] = 2; fresh--; queue.add(new int[]{x, y}); } } } } return fresh == 0 ? minutes : -1; } }复杂度分析
- 时间复杂度：
O(m * n)。每个格子最多入队一次，最多被检查一次。 - 空间复杂度：
O(m * n)。最坏情况下，队列中可能存放大量腐烂橘子。
复盘
这题的关键不是“会不会遍历四个方向”，而是能不能看出它是一个按时间分层扩散的问题。
当题目出现“每分钟”“同时扩散”“最短时间”这类描述时，要优先考虑 BFS。并且如果一开始有多个源头，比如多个腐烂橘子，就要想到多源 BFS。
下次写类似题时，可以先检查三点：
- 是否把所有起点都加入队列，而不是只从一个点开始。
- 是否用
size = queue.size()区分每一分钟。 - 是否用剩余数量
fresh判断答案和-1。
