题目链接：https://vjudge.net/problem/UVA-11624
Description
乔在迷宫中工作。不幸的是，迷宫的一部分着火了，迷宫的主人没有制定火灾的逃跑计划。请帮助乔逃离迷宫。根据乔在迷宫中的位置以及迷宫的哪个方块着火，你必须确定火焰烧到他之前，乔是否可以离开迷宫，如果能离开他能跑多快。
乔和火每分钟移动一个方格，上、下、左、右，四个方向中的一个。火势向四个方向同时蔓延。乔可以从迷宫的任何一个边界逃离迷宫。无论是乔还是火都不会到达有墙的位置。
Input
第一行输入包含一个整数，即测试次数
每个测试用例的第一行包含两个
整数R和C，用空格分隔，1≤R，C≤1000
下面R行中，每一行都包含C个字符，以及每个字符是以下之一：
# 代表墙
. 代表空地，火和乔是可通行的
J 乔在迷宫中最初的位置，火和乔是可通行的
F 代表火
在每组测试中只有一个J
Output
对于每个测试用例，如果在火蔓延的时候烧到了乔，则乔无法逃出迷宫，输出'IMPOSSIBLE'如果乔能逃出迷宫，则输出乔最快可以在几分钟内安全逃出迷宫，每组输出占一行
Sample Input
2 4 4 #### #JF# #..# #..# 3 3 ### #J. #.FSample Output
3 IMPOSSIBLE解题思路：因为火出现位置传播方向固定，所以何时何地会被火覆盖是固定的，只要先进行预处理得到某处在几分钟后会被大火覆盖，在进行BFS时经过某点时间小于这个时间就ok了，同时如果该点不会被大火覆盖那它对应的临界时间就是INF。进行两次BFS即可。
Cpp Code
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> using namespace std; const int MAXN=1010; int n,m; char g[MAXN][MAXN]; queue<pair<int,int> >q; int a[MAXN][MAXN]; int mmove[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; void bfs1() { memset(a,-1,sizeof(a)); while(!q.empty())q.pop(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]=='F') { a[i][j]=0; q.push(make_pair(i,j)); } while(!q.empty()) { pair<int,int> tmp=q.front(); q.pop(); int x=tmp.first; int y=tmp.second; for(int i=0;i<4;i++) { int tx=x+mmove[i][0]; int ty=y+mmove[i][1]; if(tx<0||ty<0||tx>=n||ty>=m)continue; if(a[tx][ty]!=-1)continue; if(g[tx][ty]=='#')continue; a[tx][ty]=a[x][y]+1; q.push(make_pair(tx,ty)); } } } int b[MAXN][MAXN]; int bfs2() { memset(b,-1,sizeof(b)); while(!q.empty())q.pop(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]=='J') { q.push(make_pair(i,j)); b[i][j]=0; } while( !q.empty() ) { pair<int,int> tmp=q.front(); q.pop(); int x=tmp.first; int y=tmp.second; if(x==0 || y==0 || x==n-1 || y==m-1) return b[x][y]+1; for(int i=0;i<4;i++) { int tx=x+mmove[i][0]; int ty=y+mmove[i][1]; if(tx<0||ty<0||tx>=n||ty>=m)continue; if(b[tx][ty]!=-1)continue; if(g[tx][ty]=='#')continue; if(a[tx][ty]!=-1 && b[x][y]+1>=a[tx][ty])continue; b[tx][ty]=b[x][y]+1; q.push(make_pair(tx,ty)); } } return -1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) scanf("%s",g[i]); bfs1(); int ans=bfs2(); if(ans==-1)printf("IMPOSSIBLE\n"); else printf("%d\n",ans); } return 0; }