烂橘子重出江湖！记得第一次见橘子还是面试被考到了orz当时就不会写如何迭代时间和出队入队hh今天再写一遍！
首先明确我们使用BFS广度优先搜索，因为可以想象橘子的腐烂是一圈圈扩散的，这很符合BFS的特点，因此我们使用队列可以实现先进先出。
其次，详细的条件有：
1、每分钟所有烂橘子都要往外扩散，即队列中原来的烂橘子全部出队，加入新的烂橘子。
2、如何迭代时间？需要保证这一分钟有新的烂橘子出现，一分钟只加一次我们的结果（之前这里还挺难的，没绕过来）
3、标记。题解中都有用cnt新鲜橘子的数量或者fresh是否还有新鲜橘子来表示是否能全部腐烂新鲜橘子，而这一点我第一次并没有想到。
代码：
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m=grid.size(), n=grid[0].size();
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int ans=0;//同一时刻应遍历所有的橘子
queue<pair<int,int>>q;
int cnt=0;//新鲜橘子的数量
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]==2)
q.push({i,j});
else if(grid[i][j]==1)
cnt++;
}
}
if(q.empty()&& cnt)//一开始就没有腐烂的橘子，但有新鲜橘子
return -1;
while(q.size())
{
int k=q.size();
for(int j=0;j<k;j++)
{
auto tmp=q.front();
q.pop();
int x=tmp.first, y=tmp.second;
for(int i=0;i<4;i++)
{
int nx=dx[i]+x,ny=dy[i]+y;
if(nx>=0&&ny>=0&&nx<m&&ny<n&&grid[nx][ny]==1)
{
grid[nx][ny]=2;
q.push({nx,ny});//把新产生的橘子放进去
cnt--;
}
}
}
if(!q.empty())
ans++;//当这一局结束，以前的烂橘子都出队了，又加入了新被腐烂的橘子，才表明成功。
}
if(cnt)
return -1;
return ans;
}
};比如说：
if(!q.empty())
ans++;//当这一局结束，以前的烂橘子都出队了，又加入了新被腐烂的橘子，才表明成功。这里，即使保证了条件2，利用了队列是否为空来判断，我觉得还挺妙的。
以及比如：
if(cnt)
return -1;结尾这里就可以这样判断是否能全部腐烂新鲜橘子。
再看一道BFS!
这题与烂橘子不一样的就在于少了一个标识，其他都差不多。
遇到边界且不是入口，直接返回路径长度。
注意：BFS需要遍历后修改数值！不然会出错滴
代码：
class Solution {
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int m=maze.size(),n=maze[0].size();
queue<pair<int,int>>q;
q.push({entrance[0],entrance[1]});
maze[entrance[0]][entrance[1]]='+';
int path=0;
while(q.size())
{
int k=q.size();
for(int j=0;j<k;j++)
{
auto tmp=q.front();
q.pop();
int x=tmp.first,y=tmp.second;
if((x==0||y==0||x==m-1||y==n-1)&&!(x==entrance[0]&&y==entrance[1]))
return path;
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=0&&ny>=0&&nx<m&&ny<n&&maze[nx][ny]=='.')
{
q.push({nx,ny});
maze[nx][ny]='+';
}
}
}
path++;
}
return -1;
}
};
完结撒花！！！！