题意：
n*m的地图中，'.'表示路,'#'表示墙，'J'表示人，'F'表示火源，火源单位时间向上下左右没有墙的地方蔓延，人单位时间走一步，问人能否在不被烧到的情况下走出地图。
人只有一个，火源可以有多个。
代码：
//两次bfs，第一次算出火源蔓延到每个点的时间，第二次bfs人的路径，人不能走到火先蔓延到的地方。 #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int inf=0x3f3f3f3f; int t,n,m,fir[1010][1010],vis[1010][1010]; int dir[4][2]={1,0,-1,0,0,1,0,-1}; char mp[1010][1010]; struct Node{ int x,y,tim; Node(){} Node(int a,int b,int c):x(a),y(b),tim(c){} }no1; queue<Node>q; void Bfs1(){ memset(vis,0,sizeof(vis)); memset(fir,inf,sizeof(fir)); queue<Node>q1; while(!q.empty()){ no1=q.front();q.pop(); q1.push(no1); vis[no1.x][no1.y]=1; fir[no1.x][no1.y]=0; } while(!q1.empty()){ no1=q1.front();q1.pop(); for(int i=0;i<4;i++){ int x=no1.x+dir[i][0],y=no1.y+dir[i][1]; if(x<0||x>=n||y<0||y>=m) continue; if(vis[x][y]||mp[x][y]=='#') continue; vis[x][y]=1; fir[x][y]=no1.tim+1; q1.push(Node(x,y,no1.tim+1)); } } } int Bfs2(int px,int py){ memset(vis,0,sizeof(vis)); queue<Node>q2; q2.push(Node(px,py,0)); vis[px][py]=1; while(!q2.empty()){ no1=q2.front();q2.pop(); if(no1.x==0||no1.x==n-1||no1.y==0||no1.y==m-1) return no1.tim; for(int i=0;i<4;i++){ int x=no1.x+dir[i][0],y=no1.y+dir[i][1]; if(x<0||x>=n||y<0||y>=m) continue; if(mp[x][y]=='#'||vis[x][y]) continue; vis[x][y]=1; ////不加这个超时了 if(no1.tim+1>=fir[x][y]) continue; q2.push(Node(x,y,no1.tim+1)); } } return -1; } int main() { scanf("%d",&t); while(t--){ int px,py; while(!q.empty()) q.pop(); scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ scanf("%s",mp[i]); for(int j=0;j<m;j++) if(mp[i][j]=='J') {px=i;py=j;} else if(mp[i][j]=='F') q.push(Node(i,j,0)); } Bfs1(); int ans=Bfs2(px,py); if(ans==-1) printf("IMPOSSIBLE "); else printf("%d ",ans+1); } return 0; }