【题目链接】：
【题目大意】：
Description
小明进入地下迷宫寻找宝藏，找到宝藏后却发生地震，迷宫各处产生岩浆，小明急忙向出口处逃跑。如果丢下宝藏，小明就能迅速离开迷宫，但小明并不想轻易放弃自己的辛苦所得。所以他急忙联系当程序员的朋友你（当然是用手机联系），并告诉你他所面临的情况，，希望你能告诉他是否能成功带着宝藏逃脱。
Input
有多组测试数据。
每组测试数据第一行是一个整数T,代表接下去的例子数。（0<=T<=10）
接下来是T组例子。
每组例子第一行是两个整数N和M。代表迷宫的大小有N行M列（0<=N,M<=1000）。
接下来是一个N*M的迷宫描述。
S代表小明的所在地。
E代表出口,出口只有一个。
.代表可以行走的地方。
！代表岩浆的产生地。（这样的地方会有多个,其个数小于等于10000）
#代表迷宫中的墙，其不仅能阻挡小明前进也能阻挡岩浆的蔓延。
小明携带者宝藏每秒只能向周围移动一格，小明不能碰触到岩浆（小明不能和岩浆处在同一格）。
岩浆每秒会向四周不是墙的地方蔓延一格。
小明先移动完成后，岩浆才会蔓延到对应的格子里。
小明能移动到出口，则小明顺利逃脱。
Output
每组测试数据输出只有一行“Yes”或者“No”。 “Yes”代表小明可以成功逃脱。否则输出“No”。
Sample Input
35 5….!S….#….!#…#E…2 2S.!E2 2SE!.
Sample Output
YesNoYes
【解题思路】：
用到两次bfs广搜，
bfs1:岩浆流到每个点的时间预处理。
bfs2:人走到每个点的同时判断时间与岩浆的时间，如果小于岩浆，则此点可以走，否则不能走
代码：
#include <stdio.h>#include <queue>#include <string.h>#include <iostream>#include <algorithm>using namespace std;int dir[4][2]= {{1,0},{-1,0},{0,-1},{0,1}};const int N=1010;const int inf=0x3f3f3f3f;char mapp[N][N];int dis[N][N];bool vis[N][N];int n,m,q;int bx,by;int ex,ey;void init(){memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));}struct node{int x,y,t;};bool ok(node ne){int x=ne.x;int y=ne.y;if(x<0||x>=n||y<0||y>=m) return false;else return true;}void bfs1(){queue<node> qa;for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){if(mapp[i][j]=='!'){dis[i][j]=0;node pre;pre.x=i,pre.y=j,pre.t=0;qa.push(pre);}}}while(!qa.empty()){node pre=qa.front();qa.pop();for(int i=0; i<4; ++i){node nex;nex.x=pre.x+dir[i][0];nex.y=pre.y+dir[i][1];nex.t=pre.t+1;if(ok(nex)&&nex.t<dis[nex.x][nex.y]){dis[nex.x][nex.y]=nex.t;qa.push(nex);}}}}void bfs2(){queue<node> qa;node pre,last;pre.x=bx,pre.y=by,pre.t=0;qa.push(pre);while(!qa.empty()){node pre=qa.front();qa.pop();if(pre.x==ex&&pre.y==ey){puts("Yes");return ;}for(int i=0; i<4; ++i){last.x=pre.x+dir[i][0];last.y=pre.y+dir[i][1];last.t=pre.t+1;if(ok(last)&&(last.x==ex)&&(last.y==ey)&&(last.t<=dis[last.x][last.y])){puts("Yes");return;}if(!vis[last.x][last.y] &&ok(last) && last.t<dis[last.x][last.y]){vis[last.x][last.y] = 1;qa.push(last);}}}puts("No");}int main(){int t;scanf("%d",&t);while(t–){init();scanf("%d%d",&n,&m);for(int i=0; i<n; ++i)scanf("%s",mapp[i]);for(int i=0; i<n; ++i)for(int j=0; j<m; ++j){if(mapp[i][j]=='S'){bx=i;by=j;}if(mapp[i][j]=='E'){ex=i;ey=j;}if(mapp[i][j]=='#'){dis[i][j]=0;}}bfs1();bfs2();}return 0;}
地球仍然转重，世间依旧善变，而我永远爱你。
