在一个矩形方阵里面，一个人要从一个位置走向另一个位置，其中某些地方有火源，每过一分钟，火源就会点燃相邻的点，同时相邻的点也变成了火源。人不能通过有火的点。问一个人能够安全地走到边界去最短时间多少？Unfortunately, portions of the maze havecaught on fire。portions of 是一些的意思。
两次bfs，首先从着火的点开始BFS进行预处理，在BFS求最短路。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #include<string> #include<cstring> using namespace std; #define inf 0x3f3f3f char a[1005][1005]; int dis[1005][1005]; int n,m,jx,jy; int nex[4][2]= {{0,1},{1,0},{0,-1},{-1,0} }; typedef struct { int x,y; } Point; int boundary(int x,int y) { return (x>=0&&x<n&&y>=0&&y<m) ; } int judge(int x,int y) { return (x==0||y==0||x==n-1|y==m-1); } void fire_bfs() { queue<Point>q; Point f1,f2; memset(dis,inf,sizeof(dis)); for(int i=0; i<n; i++) for(int j=0; j<m; j++) { if(a[i][j]=='F') { f1.x=i,f1.y=j; dis[i][j]=0; q.push(f1); } } while(!q.empty()) { f1=q.front(); q.pop(); for(int i=0; i<4; i++) { f2.x=f1.x+nex[i][0]; f2.y=f1.y+nex[i][1]; if(boundary(f2.x,f2.y)&&a[f2.x][f2.y]=='.'&&dis[f2.x][f2.y]>dis[f1.x][f1.y]+1) { dis[f2.x][f2.y]=dis[f1.x][f1.y]+1; q.push(f2); } } } } int bfs() { queue<Point>q; Point f1,f2; f1.x=jx,f1.y=jy; dis[jx][jy]=0; q.push(f1); while(!q.empty()) { f1=q.front(); if(judge(f1.x,f1.y)) return dis[f1.x][f1.y]+1;//注意判断的位置 q.pop(); for(int i=0; i<4; i++) { f2.x=f1.x+nex[i][0]; f2.y=f1.y+nex[i][1]; if(boundary(f2.x,f2.y)&&a[f2.x][f2.y]=='.'&&dis[f2.x][f2.y]>dis[f1.x][f1.y]+1) { dis[f2.x][f2.y]=dis[f1.x][f1.y]+1; q.push(f2); } } } return 0; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { getchar(); for(int j=0; j<m; j++) { scanf("%c",&a[i][j]); if(a[i][j]=='J') jx=i,jy=j; } } fire_bfs(); int c=bfs(); if(c==0) printf("IMPOSSIBLE "); else printf("%d ",c); } return 0; }