[bfs] fzu oj 2196 Escape

题意：

一个迷宫里面从开始走到终点的最短步数。

但是这个迷宫里面有许多的火山，，会喷岩浆，岩浆每秒向四周蔓延，岩浆到过的点不能走，但是人的移动优先于岩浆。

意思就是，如果某一个时刻，岩浆和人同时到达，那么如果这个点是出口的话，这个点是可以走的。

思路：

首先bfs预处理所有的点火山蔓延到的最小时间，就是将所有火山压进队做bfs。

接着用人做一遍bfs，注意考虑上面的那个人的移动优先于岩浆。

代码：

#include"cstdlib"#include"cstdio"#include"cstring"#include"cmath"#include"queue"#include"algorithm"#include"iostream"#include"map"using namespace std;#define eps 1e-13#define ll __int64int time[1234][1234];int used[1234][1234];int n,m;char mp[1234][1234];int dis[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};struct node{int x,y,t;};void bfs1(){for(int i=0; i<n; i++) for(int j=0; j<m; j++) time[i][j]=-1;node cur,next;queue<node>q;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(mp[i][j]=='!'){cur.x=i;cur.y=j;cur.t=0;time[i][j]=0;q.push(cur);}}}while(!q.empty()){cur=q.front();q.pop();for(int i=0; i<4; i++){next.x=cur.x+dis[i][0];next.y=cur.y+dis[i][1];next.t=cur.t+1;if(next.x<0 || next.y<0 || next.x>=n || next.y>=m || mp[next.x][next.y]=='#' || time[next.x][next.y]!=-1) continue;time[next.x][next.y]=next.t;q.push(next);}}return ;}int bfs2(){for(int i=0; i<n; i++) for(int j=0; j<m; j++) used[i][j]=0;node cur,next;queue<node>q;for(int i=0; i<n; i++){for(int j=0; j<m; j++){if(mp[i][j]=='S'){cur.x=i;cur.y=j;cur.t=0;used[i][j]=1;q.push(cur);}}}while(!q.empty()){cur=q.front();q.pop();for(int i=0; i<4; i++){next.x=cur.x+dis[i][0];next.y=cur.y+dis[i][1];next.t=cur.t+1;if(next.x<0 || next.y<0 || next.x>=n || next.y>=m || mp[next.x][next.y]=='#' || used[next.x][next.y] || time[next.x][next.y]<next.t) continue;used[next.x][next.y]=1;if(mp[next.x][next.y]=='E') return 1;else if(next.t!=time[next.x][next.y]) q.push(next);}}return 0;}int main(){int t;cin>>t;while(t–){scanf("%d%d",&n,&m);for(int i=0; i<n; i++) scanf("%s",mp[i]);bfs1();int ans=bfs2();puts(ans?"Yes":"No");}return 0;}

我想有一天和你去旅行。去那没有去过的地方，