题目连接：http://acm.hust.edu.cn/vjudge/problem/28833
/* 首先对整个图bfs一次得到火焰燃烧的时刻表 之后在bfs搜路径时加一个火烧表的判断 坑点在于：如果时刻表等于0应该是从未烧过。。。如果不加以区分就会wa */ #include <bits/stdc++.h> #define scan(x) scanf("%d",&x) #define M(x) memset(x,0,sizeof(x)) #define REF(i,n) for(int i=1;i<=n;i++) using namespace std; const int Max=1e3+10; char mat[Max][Max]; int book[Max][Max]; int vis[Max][Max]; int n,m,stx,sty; struct node { int x,y,step; node(){x=y=step=0;} node(int xx,int yy,int ss):x(xx),y(yy),step(ss){} }; int nex[4][2]={0,1,1,0,0,-1,-1,0}; queue<node>que1; void bfs1() { M(book);M(vis); node u,v; while(!que1.empty()) { u=que1.front(); que1.pop(); for(int k=0;k<4;k++) { v.x=u.x+nex[k][0]; v.y=u.y+nex[k][1]; v.step=u.step+1; if(v.x<1||v.y<1||v.x>n||v.y>m) continue; if(mat[v.x][v.y]=='#') continue; if(book[v.x][v.y]) continue; book[v.x][v.y]=v.step; que1.push(v); } } } int bfs2() { M(vis); queue<node>que; node u,v; que.push(node(stx,sty,0)); vis[stx][sty]=1; while(!que.empty()) { u=que.front(); que.pop(); for(int k=0;k<4;k++) { v.x=u.x+nex[k][0]; v.y=u.y+nex[k][1]; v.step=u.step+1; if(v.x<1||v.y<1||v.x>n||v.y>m) return v.step; if(book[v.x][v.y]!=0&&book[v.x][v.y]<=v.step) continue;//book[i][j]!=0 if(mat[v.x][v.y]=='#'||mat[v.x][v.y]=='F') continue;//不能把从未着火的点也排除 if(vis[v.x][v.y]) continue; vis[v.x][v.y]=1; que.push(v); } } return -1; } int main() { int T; for(scan(T);T;T--) { cin>>n>>m;getchar(); while(!que1.empty()) que1.pop(); REF(i,n) { REF(j,m) { scanf("%c",&mat[i][j]); if(mat[i][j]=='J') stx=i,sty=j; if(mat[i][j]=='F') que1.push(node(i,j,0)); } getchar(); } bfs1(); int ans=bfs2(); if(ans!=-1) cout<<ans<<endl; else cout<<"IMPOSSIBLE"<<endl; } return 0; }