腐烂的橘子 力扣bfs

BFS用来搜索最短路径的解法是比较合适的。

比如求最少步数的解，最少交换次数的解，最快走出迷宫等等，因为bfs搜索过程中遇到的第一个解一定是离最初位置最近的，所以遇到第一个解，一定就是最优解，此时搜索算法可以终止。

DFS用来搜索全部的解。

class Solution {
public://bfs最短路径 队列
   int dis[11][11],cut,ans,tx,ty;
   int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    int orangesRotting(vector<vector<int>>& grid) {
     queue<pair<int,int>>q;//队里存的都是腐烂的橘子
     memset(dis,-1,sizeof(dis));
    int n=grid.size(),m=grid[0].size(),i,j;
    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
    {
        if(grid[i][j]==2)//腐烂
        {
            q.push(make_pair(i,j));
            dis[i][j]=0;
//现在所有腐烂的橘子的位置都是0，其他位置是-1，这个用来记录时间，还可以标志这个位置的橘子是否新鲜
        }
        else if(grid[i][j]==1)//新鲜
        cut++;
    }
    while(!q.empty()){
        pair<int,int>x=q.front();q.pop();
       for(i=0;i<4;i++)
       {
         tx=dx[i]+x.first;
         ty=dy[i]+x.second;
if(tx>=0&&tx<n&&ty>=0&&ty<m&&grid[tx][ty]!=0&&dis[tx][ty]==-1)
   { dis[tx][ty]=dis[x.first][x.second]+1;//这个背腐烂的橘子的时间是传染给他腐烂的橘子加1
      q.push(make_pair(tx,ty));//加入新腐烂的橘子
        cut--;
        ans=max(ans,dis[tx][ty]);
        if(cut==0) break;
       }}   }
    return cut?-1:ans;  }};