在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
做广度优先搜索，先遍历记录下来新鲜橘子的个数，同时把腐烂橘子坐标都压入队列。用一个数组记录每个点的腐烂时间，初始腐烂的位0，其余全为-1。不断从队列中取出腐烂节点，判断上下左右四个节点，如果符合要求就把他腐烂掉，同时更新腐烂时间。等队列为空时判断还有没有新鲜橘子就可以了。
1 class Solution { 2 private: 3 int dis[10][10]; 4 int dir_x[4]={0, 1, 0, -1}; 5 int dir_y[4]={1, 0, -1, 0}; 6 7 public: 8 int orangesRotting(vector<vector<int>>& grid) { 9 int row=grid.size(); 10 if(!row) 11 return 0; 12 int col=grid[0].size(); 13 int fresh=0; 14 int ans=0; 15 16 queue<pair<int,int>> q; 17 for(int i=0;i<row;++i) 18 for(int j=0;j<col;++j){ 19 if(grid[i][j]==1) 20 ++fresh; 21 else if(grid[i][j]==2){ 22 q.push(make_pair(i,j)); 23 } 24 dis[i][j]=grid[i][j]==2?0:-1; 25 } 26 if(!fresh) 27 return 0; 28 while(!q.empty()){ 29 pair<int,int>pos=q.front();q.pop(); 30 for(int i=0;i<4;++i){ 31 int tx=pos.first+dir_x[i]; 32 int ty=pos.second+dir_y[i]; 33 if(tx<0 || tx>=row || ty<0 || ty>=col || !grid[tx][ty] || dis[tx][ty]!=-1) 34 continue; 35 dis[tx][ty]=dis[pos.first][pos.second]+1; 36 q.push(make_pair(tx,ty)); 37 --fresh; 38 ans=dis[tx][ty]; 39 if(!fresh) 40 break; 41 } 42 } 43 return fresh==0?ans:-1; 44 } 45 };
原文：https://www.cnblogs.com/rookiez/p/13400070.html