传送门UVA11624

描述

Joe works in a maze. Unfortunately, portions of the maze havecaught on fire, and the owner of the maze neglected to create a fireescape plan. Help Joe escape the maze.Given Joe’s location in the maze and which squares of the mazeare on fire, you must determine whether Joe can exit the maze beforethe fire reaches him, and how fast he can do it.Joe and the fire each move one square per minute, vertically orhorizontally (not diagonally). The fire spreads all four directionsfrom each square that is on fire. Joe may exit the maze from anysquare that borders the edge of the maze. Neither Joe nor the firemay enter a square that is occupied by a wall.

输入

The first line of input contains a single integer, the number of testcases to follow. The first line of each test case contains the twointegers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. Thefollowing R lines of the test case each contain one row of the maze. Each of these lines contains exactlyC characters, and each of these characters is one of:

12341. #, a wall2. ., a passable square3. J, Joe’s initial position in the maze, which is a passable square4. F, a square that is on fire

There will be exactly one J in each test case.

输出

For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before thefire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.

样例

Input

1234567891024 4#####JF##..##..#3 3####J.#.F

Output

123IMPOSSIBLE

题解

题意：迷宫逃脱，一开始有多个火焰源，火焰每单位时间向四周蔓延一格，人每单位可以向四周移动一格，人可以从任意边界逃脱，但是不能碰到火焰，求最短逃脱时间。先多起点bfs预处理出每一个格子的火焰到达时间，然后对人进行bfs即可。

Code

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include<stdio.h>#include<string.h>#include<queue>#define INIT(a,b) memset(a,b,sizeof(a))#define LL long longusing namespace std;const int inf=0x3f3f3f3f;const int N=1e3+7;const int mod=1e9+7;int t,n,m,jx,jy;char mp[N][N];int fi[N][N],vis[N][N];int rec[4][2]={1,0,-1,0,0,1,0,-1};struct node{ int x,y,time;};inline bool away(int i,int j){ if(i==0||i==n-1||j==0||j==m-1)return true; else return false;}inline bool judge(int i,int j){ if(i<0||i>=n||j<0||j>=m||vis[i][j]||mp[i][j]=='#')return false; return true;}queue<node> fque;void fire(){ while(!fque.empty()){ node q=fque.front();fque.pop(); for(int i=0;i<4;i++){ int nx=q.x+rec[i][0],ny=q.y+rec[i][1]; if(judge(nx,ny)){ fque.push((node){nx,ny,q.time+1}); fi[nx][ny]=q.time+1; vis[nx][ny]=1; } } }}int bfs(){ INIT(vis,0); queue<node> que; que.push((node){jx,jy,1}); vis[jx][jy]=1; while(!que.empty()){ node q=que.front();que.pop(); if(away(q.x,q.y)) return q.time; for(int i=0;i<4;i++){ int nx=q.x+rec[i][0],ny=q.y+rec[i][1]; if(judge(nx,ny)&&q.time+1<fi[nx][ny]){ que.push((node){nx,ny,q.time+1}); vis[nx][ny]=1; } } } return -1;}int main(){ scanf("%d",&t); while(t--){ INIT(fi,inf),INIT(vis,0); scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ getchar(); for(int j=0;j<m;j++){ scanf("%c",&mp[i][j]); if(mp[i][j]=='J') jx=i,jy=j; if(mp[i][j]=='F') { fque.push((node){i,j,1}); vis[i][j]=1; fi[i][j]=1; } } } fire(); int ans=bfs(); if(ans==-1) printf("IMPOSSIBLE\n"); else printf("%d\n",ans); } return 0;}