力扣HOT100（48）图论-腐烂的橘子

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