994. 腐烂的橘子
题目链接：994. 腐烂的橘子
代码如下：
//广度优先遍历
//参考链接:https://leetcode.cn/problems/rotting-oranges/solutions/2773461/duo-yuan-bfsfu-ti-dan-pythonjavacgojsrus-yfmh
class Solution
{
public:int orangesRotting(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();int fresh=0;vector<pair<int,int>> q;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.emplace_back(i,j);//把一开始就腐烂的放到队列中}}}int res=-1;while(!q.empty()){res++;//过了一分钟vector<pair<int,int>> nxt;for(auto& [x,y]:q)//遍历已腐烂的橘子{for(int i=0;i<4;i++)//遍历4个方向{int nextX=x+dir[i][0];int nextY=y+dir[i][1];if(nextX<0||nextX>=m||nextY<0||nextY>=n) continue;if(grid[nextX][nextY]!=1) continue;fresh--;grid[nextX][nextY]=2;nxt.emplace_back(nextX,nextY);}}q=move(nxt);}return fresh?-1:max(res,0);}
private:int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右
};