994. 腐烂的橘子

994. 腐烂的橘子

题目链接：994. 腐烂的橘子

代码如下：

//广度优先遍历
//参考链接:http://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}};//上下左右
};