LeetCode 994中等多源 BFS
腐烂的橘子 图解题解
这道题到底在问什么
腐烂只在上下左右四个方向、一格一格传，空格 0 挡路（橘子腐烂传不过空格）。求把所有新鲜橘子都传染完所需的分钟数；只要结束后还剩一个新鲜橘子，就说明它被空格围死、永远烂不到，返回 -1。
最优解：一步一步想明白
- 3别盯着某一个橘子算。把「所有已经烂掉的橘子」一起当 BFS 的起点同时入队，像水波一样一圈圈往外漫：第一圈是 1 分钟后被染的、第二圈是 2 分钟后被染的……漫到最后一圈所用的圈数，就是答案分钟数。
- 4烂橘子=源点(1个)，新鲜=9，空格=2把当前全部 1 个烂橘子一次性放进队列，它们都算「第 0 分钟」的源头。9 个绿色新鲜橘子等着被传染，2 个灰色空格会挡住腐烂的去路。下面开始一分钟一分钟地往外漫。
- 5源烂橘子=(0,0)，目标新鲜=(1,0)烂橘子 (0,0) 把相邻的新鲜橘子 (1,0) 传染。这是 (1,0) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 1 分钟烂掉，分钟数定死不再变。
- 6(1,0) 腐烂于第 1 分钟(1,0) 染成腐烂、标记腐烂分钟 1，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 7源烂橘子=(0,0)，目标新鲜=(0,1)烂橘子 (0,0) 把相邻的新鲜橘子 (0,1) 传染。这是 (0,1) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 1 分钟烂掉，分钟数定死不再变。
- 8(0,1) 腐烂于第 1 分钟(0,1) 染成腐烂、标记腐烂分钟 1，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 9分钟数 → 1第 1 分钟这一圈相邻的新鲜橘子都传染完了，时钟走到 1。队列里现在装着刚烂的橘子，它们将在下一分钟继续往外漫一圈。
- 10源烂橘子=(1,0)，目标新鲜=(1,1)烂橘子 (1,0) 把相邻的新鲜橘子 (1,1) 传染。这是 (1,1) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 2 分钟烂掉，分钟数定死不再变。
- 11(1,1) 腐烂于第 2 分钟(1,1) 染成腐烂、标记腐烂分钟 2，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 12源烂橘子=(0,1)，目标新鲜=(0,2)烂橘子 (0,1) 把相邻的新鲜橘子 (0,2) 传染。这是 (0,2) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 2 分钟烂掉，分钟数定死不再变。
- 13(0,2) 腐烂于第 2 分钟(0,2) 染成腐烂、标记腐烂分钟 2，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 14分钟数 → 2第 2 分钟这一圈相邻的新鲜橘子都传染完了，时钟走到 2。队列里现在装着刚烂的橘子，它们将在下一分钟继续往外漫一圈。
- 15源烂橘子=(1,1)，目标新鲜=(2,1)烂橘子 (1,1) 把相邻的新鲜橘子 (2,1) 传染。这是 (2,1) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 3 分钟烂掉，分钟数定死不再变。
- 16(2,1) 腐烂于第 3 分钟(2,1) 染成腐烂、标记腐烂分钟 3，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 17源烂橘子=(0,2)，目标新鲜=(0,3)烂橘子 (0,2) 把相邻的新鲜橘子 (0,3) 传染。这是 (0,3) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 3 分钟烂掉，分钟数定死不再变。
- 18(0,3) 腐烂于第 3 分钟(0,3) 染成腐烂、标记腐烂分钟 3，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 19分钟数 → 3第 3 分钟这一圈相邻的新鲜橘子都传染完了，时钟走到 3。队列里现在装着刚烂的橘子，它们将在下一分钟继续往外漫一圈。
- 20源烂橘子=(2,1)，目标新鲜=(2,2)烂橘子 (2,1) 把相邻的新鲜橘子 (2,2) 传染。这是 (2,2) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 4 分钟烂掉，分钟数定死不再变。
- 21(2,2) 腐烂于第 4 分钟(2,2) 染成腐烂、标记腐烂分钟 4，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 22源烂橘子=(0,3)，目标新鲜=(1,3)烂橘子 (0,3) 把相邻的新鲜橘子 (1,3) 传染。这是 (1,3) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 4 分钟烂掉，分钟数定死不再变。
- 23(1,3) 腐烂于第 4 分钟(1,3) 染成腐烂、标记腐烂分钟 4，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 24分钟数 → 4第 4 分钟这一圈相邻的新鲜橘子都传染完了，时钟走到 4。队列里现在装着刚烂的橘子，它们将在下一分钟继续往外漫一圈。
- 25源烂橘子=(2,2)，目标新鲜=(2,3)烂橘子 (2,2) 把相邻的新鲜橘子 (2,3) 传染。这是 (2,3) 第一次被碰到 —— 多源 BFS 第一次碰到就是最早，所以它就在第 5 分钟烂掉，分钟数定死不再变。
- 26(2,3) 腐烂于第 5 分钟(2,3) 染成腐烂、标记腐烂分钟 5，并加进队列尾。下一分钟轮到它，再去传染它自己的新鲜邻居 —— 队列严格按分钟（层）推进，保证每个橘子记的都是最早被传染的时刻。
- 27分钟数 → 5第 5 分钟这一圈相邻的新鲜橘子都传染完了，时钟走到 5。队列里现在装着刚烂的橘子，它们将在下一分钟继续往外漫一圈。
- 28答案 = 5 分钟队列空了，水波漫遍每个能到的橘子，最后一个在第 5 分钟烂掉。最大的腐烂分钟数 5 就是答案。如果此刻还剩任何一个新鲜橘子，就该返回 -1，本例全烂完没有死角。
完整代码（Python / C++ / Java）
Python
from collections import deque
def orangesRotting(grid):
R, C = len(grid), len(grid[0])
q, fresh = deque(), 0
for i in range(R):
for j in range(C):
if grid[i][j] == 2: q.append((i, j))
elif grid[i][j] == 1: fresh += 1
minutes = 0
dirs = ((1,0),(-1,0),(0,1),(0,-1))
while q and fresh:
for _ in range(len(q)):
i, j = q.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < R and 0 <= nj < C \
and grid[ni][nj] == 1:
grid[ni][nj] = 2
fresh -= 1
q.append((ni, nj))
minutes += 1
return -1 if fresh else minutesC++
int orangesRotting(vector<vector<int>>& grid){
int R = grid.size(), C = grid[0].size();
queue<pair<int,int>> q; int fresh = 0;
for(int i=0;i<R;i++) for(int j=0;j<C;j++){
if(grid[i][j]==2) q.push({i,j});
else if(grid[i][j]==1) fresh++;
}
int minutes = 0, dir[5] = {-1,0,1,0,-1};
while(!q.empty() && fresh){
int sz = q.size();
for(int s=0;s<sz;s++){
auto [i,j] = q.front(); q.pop();
for(int d=0;d<4;d++){
int ni=i+dir[d], nj=j+dir[d+1];
if(ni<0||nj<0||ni>=R||nj>=C) continue;
if(grid[ni][nj]!=1) continue;
grid[ni][nj]=2; fresh--; q.push({ni,nj});
}
}
minutes++;
}
return fresh ? -1 : minutes;
}Java
class Solution {
public int orangesRotting(int[][] grid) {
int R = grid.length, C = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) {
if (grid[i][j] == 2) q.add(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
int minutes = 0;
int[] dir = {-1, 0, 1, 0, -1};
while (!q.isEmpty() && fresh > 0) {
int sz = q.size();
for (int s = 0; s < sz; s++) {
int[] c = q.poll();
for (int d = 0; d < 4; d++) {
int ni = c[0] + dir[d], nj = c[1] + dir[d + 1];
if (ni < 0 || nj < 0 || ni >= R || nj >= C) continue;
if (grid[ni][nj] != 1) continue;
grid[ni][nj] = 2;
fresh--;
q.add(new int[]{ni, nj});
}
}
minutes++;
}
return fresh > 0 ? -1 : minutes;
}
}复杂度
时间
O(行×列)
每个格子最多入队一次、出队一次，每次看四个方向。时间 O(行×列)，空间 O(行×列) 是队列。一次多源 BFS 就把所有橘子的腐烂时刻全算出来。
空间
O(行×列)
每个格子最多入队一次、出队一次，每次看四个方向。时间 O(行×列)，空间 O(行×列) 是队列。一次多源 BFS 就把所有橘子的腐烂时刻全算出来。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 腐烂的橘子 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么所有烂橘子要同时入队？+
腐烂是同时发生的，多源 BFS 一圈代表一分钟，谁先碰到谁就先烂，自动得到最早时刻。
怎么判 -1？+
BFS 漫完后还有新鲜计数没归零，说明那些橘子被空格围死，永远烂不到。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 腐烂的橘子 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。