广度优先搜索处理橘子腐烂问题

广度优先搜索处理橘子腐烂问题

在给定的网格中，每个单元格可以有一下三个值之一：
①值为0，代表空单元格
②值为1，代表新鲜橘子
③值为2，代表腐烂橘子

每分钟，任何与腐烂橘子相邻的4个方向（上下左右）相邻的橘子都会腐烂。返回直到单元格没有新鲜橘子为止所必须经过的最小时间。如果不可能则返回-1。

分析：该问题是模拟广度搜索的过程，从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索到的路径就是从起点开始的最短合法路径。

class Solution
{public:int orangesRotting(vector<vector<int>>& grid){int directions[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//四个方向int row=grid.size();int colum=grid[0].size();int time=0;//完成感染所需时间queue<pair<int,int>> q;//保存腐烂橘子int count=0;//新鲜橘子的数量for(int i=0;i!=row;i++){for(int j=0;j!=colum;j++){if(grid[i][j]==1) count++;if(grid[i][j]==2) q.push({i,j});}}if(count==0) return time;while(!q.empty()){time++;for(int j=q.size();j>0;j--){auto curr=q.front();q.pop();for(int k=0;k!=4;k++){int x=curr.first+directions[k][0];int y=curr.second+directions[k][1];if(x<0 || x>row-1 || y<0 || y>colum-1 || grid[x][y]==0) continue;if(grid[x][y]==1){grid[x][y]=2;count--;q.push({x,y});}}if(count==0) return time;}}return -1;}
};