题目链接：https://vjudge.net/problem/UVA-11624
题意：给一个1000×1000的矩阵，有几个着火点和Joe，着火点和Joe每个单位时间均移动一个单位，求Joe逃出的最短时间。
思路：
先预处理，对每一个Fire进行一次bfs，更新cnt[i][j]，它表示(i,j)的着火时间，注意多个Fire能到达(i,j)时要使cnt[i][j]最小，并且该bfs中的判断语句if(cnt[xx][yy]<=ss) continue能够避免走重复的路径，因此不用标记数组。得到cnt数组后，再对Joe进行一次bfs即可，需要标记数组vis。
AC代码：
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int go[4][2]={-1,0,0,1,1,0,0,-1};
int T,n,m,jx,jy,cnt[1005][1005],vis[1005][1005];
char mp[1005][1005];
vector<PII> vc;
struct node{
int x,y,s;
}tmp;
void bfs1(int x,int y){
queue<node> que;
cnt[x][y]=0;
tmp.x=x,tmp.y=y,tmp.s=0;
que.push(tmp);
while(!que.empty()){
node now=que.front();que.pop();
int nx=now.x,ny=now.y,ns=now.s;
for(int i=0;i<4;++i){
int xx=nx+go[i][0],yy=ny+go[i][1],ss=ns+1;
if(xx<=0||xx>n||yy<=0||yy>m||mp[xx][yy]=='#') continue;
if(cnt[xx][yy]<=ss) continue;
cnt[xx][yy]=ss;
tmp.x=xx,tmp.y=yy,tmp.s=ss;
que.push(tmp);
}
}
}
bool onborder(int x,int y){
return x==1||x==n||y==1||y==m;
}
int bfs2(int x,int y){
queue<node> que;
tmp.x=x,tmp.y=y,tmp.s=0;
que.push(tmp);
vis[x][y]=1;
while(!que.empty()){
node now=que.front();que.pop();
int nx=now.x,ny=now.y,ns=now.s;
if(onborder(nx,ny)) return ns+1;
for(int i=0;i<4;++i){
int xx=nx+go[i][0],yy=ny+go[i][1],ss=ns+1;
if(xx<=0||xx>n||yy<=0||yy>m||mp[xx][yy]=='#') continue;
if(vis[xx][yy]) continue;
if(cnt[xx][yy]<=ss) continue;
vis[xx][yy]=1;
tmp.x=xx,tmp.y=yy,tmp.s=ss;
que.push(tmp);
}
}
return -1;
}
int main(){
scanf("%d",&T);
while(T--){
vc.clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
cnt[i][j]=inf;
vis[i][j]=0;
scanf(" %c",&mp[i][j]);
if(mp[i][j]=='J') jx=i,jy=j;
if(mp[i][j]=='F') vc.push_back(make_pair(i,j));
}
for(int i=0;i<vc.size();++i)
bfs1(vc[i].first,vc[i].second);
int t=bfs2(jx,jy);
if(t==-1)
printf("IMPOSSIBLE\n");
else
printf("%d\n",t);
}
return 0;
}