为什么必须用「多源 BFS」？
先想：如果只有一个腐烂橘子，怎么做？
这就是普通的单源 BFS：
- 把初始腐烂橘子入队（第 0 层）
- 每分钟处理队列里当前层的所有橘子，把它们相邻的新鲜橘子腐烂，作为下一层入队
- 每处理完一层，时间加 1
- 最后看有没有剩下的新鲜橘子
但题目里可能有多个初始腐烂橘子！
如果对每个腐烂橘子单独做一次 BFS，再取每个新鲜橘子的最小腐烂时间，时间复杂度会变成O(k*nm)（k 是初始腐烂橘子数），效率很低。
多源 BFS 的巧妙之处
所有初始腐烂橘子，都是 BFS 的第 0 层节点，同时入队！
- 相当于所有腐烂橘子同时开始扩散
- 一次遍历就能得到所有新鲜橘子的最短腐烂时间
- 时间复杂度只有
O(nm)，和单源 BFS 一样
核心思路（一句话讲透）
把所有初始腐烂的橘子同时放进队列，然后像层序遍历一样，一层一层处理：
- 每一层对应一分钟
- 处理当前层的所有腐烂橘子，把它们相邻的新鲜橘子腐烂，放进下一层
- 最后如果还有新鲜橘子没被处理，返回
-1，否则返回总层数（时间）
class Solution { public: int orangesRotting(vector<vector<int>>& grid) { int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int m = grid.size();//行数 int n = grid[0].size();//列数 int fresh = 0; int mins = 0; queue<pair<int,int>> q; for(int i = 0;i<m;i++){ for(int j = 0;j<n;j++){ if(grid[i][j] == 2){ q.push({i,j}); } else if(grid[i][j] == 1){ fresh++; } } } while(!q.empty()&& fresh>0){ //当q不为空且fresh新鲜数大于零 //有新鲜的就要腐烂 int size = q.size();//初始腐烂的个数 //往四个方向腐烂 for(int i = 0;i<size;i++){ //取出队首的坐标 int x = q.front().first; int y = q.front().second; q.pop(); //左方： if(y-1>=0 && grid[x][y-1] == 1 ){ //腐烂 grid[x][y-1] = 2; fresh--; q.push({x,y-1}); } //右方 if(y+1<n && grid[x][y+1] == 1){ grid[x][y+1] = 2; fresh--; q.push({x,y+1}); } //上方 if(x-1>=0&&grid[x-1][y] == 1){ grid[x-1][y] = 2; fresh--; q.push({x-1,y}); } //下方 if(x+1<m && grid[x+1][y] == 1){ grid[x+1][y] = 2; fresh--; q.push({x+1,y}); } } mins++; } return fresh == 0 ? mins : -1; } };
