搜索的第一次总结：水灾（flood）
前几篇都讲了关于搜索的内容，现在就来做做习题吧！！！
（没看以前我的文章的人请看专栏：https://blog.csdn.net/mayuteng1/category_13083478.html?spm=1001.2014.3001.5482）
注：名字别管，其实就是Robin！！！
题目描述
这天 SB Robin 正打着游戏，正思考着怎么才能过关，突然，bong 的一声，家里的水管全爆了！！！
已知 SB Robin 的家可以用一个 n*m 的网格表示。
SB Robin 每秒钟可以走到上下左右 4 个方向的相邻格中的一个没有水的格子（他不喜欢踩水），而所有有水的格子每秒也会向四周的空格蔓延（上下左右四个格子）。显然最开始有水的格子是那些水管的位置。
SB Robin 家还有一些障碍格，比如他家的 60 英寸的大电视，比如一些紫檀木家具，还有墙也是一种障碍……，水跟 SB Robin 都不能进入这个格。
当他到达地图边界时就可以认为他逃出了他家。
请问SB Robin 怎么以最短的时间逃出家。 注意：
1.等 SB Robin 反应过来时已经过去了1秒。
2.开始时，水可能不止一处。
输入格式
第一行，两个整数 n 和 m，表示 SB Robin 家的行数跟列数。
接下来是一个 n*m 的字符串矩阵。其中，"."表示空地，水和 SB Robin 都能进去，"s"表示 SB Robin 所在位置，"w"表示爆掉的水管的位置，"#"表示障碍和墙， 水和 SB Robin 都不能进去。
输出格
输入数据仅一行，能逃出去，则输出一个整数，表示 SB Robin 逃出家的最短时间。
如果 SB Robin 出不去，则输出"IMPOSSIBLE"(不含引号)。
输入输出样例
输入数据 1
4 4 #### #sw# #..# #..#输出数据 1
3输入数据 2
3 4 #### #s.# #.w.输出数据 2
IMPOSSIBLE数据范围与约定
对于20%的数据，1<=n,m<=100；
对于100%的数据，1<=n,m<=1000。
（正在看我的博客的人在这里其实可以自己先试着打一下代码！）
————————我是分割线——————————
这题一眼搜索啊！
不过这题用DFS的话肯定会超时的（而且其实我这道题连DFS该怎么打都不知道……）！所以这道题我们只能用广度优先搜索（BFS）来做！！
代码如下：（精髓都在注释中！）：
#include<bits/stdc++.h> using namespace std; long long n,m;//n,m表示矩阵的长和宽 long long a[1005][1005],xx,yy;//a数组用来判断这个地方是否是墙,xx/yy分别表示Robin的坐标 long long minn=INT_MAX;//minn表示Robin到边缘的最短距离 long long dx[]={-1,1,0,0},dy[]={0,0,-1,1};//方向数组 long long b[1005][1005],c[1005][1005];//b数组表示水流到这个地方的最短距离，c数组表示Robin到这个地方的最短距离 queue<pair<int,int>> q;//队列（用来打BFS） void bfs1()//第一个BFS，用来枚举水 { while(!q.empty()) { int x=q.front().first,y=q.front().second;//获取x和y坐标 q.pop();//弹出 for(int i=0;i<4;i++)//枚举四个方向 { int nx=x+dx[i],ny=y+dy[i]; if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&b[nx][ny]==0&&a[nx][ny]!=-1) { //当x和y坐标在规定范围内且这个地方没有来过且这个地方不是墙，则加入队列 b[nx][ny]=b[x][y]+1;//标记，这个地方的步数比原来的地方的步数多一 q.push({nx,ny}); } } } } void bfs2()//第二个BFS，用来枚举Robin { q.push({xx,yy});//加入Robin的x和y坐标 while(!q.empty()) { int x=q.front().first,y=q.front().second; q.pop(); for(int i=0;i<4;i++) { int nx=x+dx[i],ny=y+dy[i]; if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&c[nx][ny]==INT_MAX-1&&a[nx][ny]!=-1&&b[nx][ny]+1>c[x][y]) { //多了一个条件，那就是水流到这一格的最小步数要比Robin到这一格的最小步数多1 c[nx][ny]=c[x][y]+1;//累计 q.push({nx,ny});//加入新的x和y坐标 } } } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { char ch; for(int j=1;j<=m;j++) { cin>>ch; if(ch=='#')a[i][j]=-1,c[i][j]=INT_MAX;//如果是墙则a[i][j]=-1,c[i][j]也要标记 else if(ch=='s')xx=i,yy=j,a[i][j]=1,c[i][j]=0;//获取Robin的坐标 else if(ch=='w')q.push({i,j}),a[i][j]=2,c[i][j]=INT_MAX;//由于可能有多处水管爆裂，所以在这里就要入队了 else c[i][j]=INT_MAX-1;//空地的话，c[i][j]=INT_MAX-1 } } bfs1();//第一个BFS bfs2();//第二个BFS //枚举矩阵的四周，假如Robin到这一格的时间比水到这一格的时间短，则minn=min(minn,Robin到这一格的时间) for(int i=1;i<=n;i++) { if(b[i][1]>c[i][1])minn=min(minn,c[i][1]); if(b[i][m]>c[i][m])minn=min(minn,c[i][m]); } for(int i=1;i<=m;i++) { if(b[1][i]>c[1][i])minn=min(minn,c[1][i]); if(b[n][i]>c[n][i])minn=min(minn,c[n][i]); } if(minn==INT_MAX)cout<<"IMPOSSIBLE";//加入minn没有更新最小值，则Robin逃离不了了 else cout<<minn+1;//否则输出minn+1 return 0; }