Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze. Given Joe’s location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it. Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square that is on fire. Joe may exit the maze from any square that borders the edge of the maze. Neither Joe nor the fire may enter a square that is occupied by a wall.
Input：
The first line of input contains a single integer, the number of test cases to follow. The first line of each test case contains the two integers R and C, separated by spaces, with 1 ≤ R, C ≤ 1000. The following R lines of the test case each contain one row of the maze. Each of these lines contains exactly C characters, and each of these characters is one of: • #, a wall • ., a passable square • J, Joe’s initial position in the maze, which is a passable square • F, a square that is on fire There will be exactly one J in each test case.
Output：
For each test case, output a single line containing ‘IMPOSSIBLE’ if Joe cannot exit the maze before the fire reaches him, or an integer giving the earliest time Joe can safely exit the maze, in minutes.
题面翻译：
一个迷宫着火了，火每分钟向四个方向扩散，人一分钟也可以向四个方向走一步，人和火都不能碰到墙，问人能否逃出迷宫？（走出边界即算逃出迷宫）如果能，最短用时为多少？
分析：
先让火向四周走一步，再让人走一步，因为火即将蔓延到的地方人是不能走的。
那么抽象一点，就是分别以火（可能不止一个）和人为起点向四周一层层搜索，看看人能否走出边界。
这里有一个要注意的地方，广搜一般都是while（！q.empty)，但是这道题里不行，必须火走一步，人走一步。
还有一个思路就是预处理火会在几分钟到达某点，再让人去走。
最后吐槽一下自己写了初始化函数却忘记执行，而wa的悲痛经历。
代码详解：
一些全局变量
typedef struct{ int x,y; int step; }pos; int ans; int direct[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; queue<pos>Joe; queue<pos>fire; char maze[1005][1005]; //记录迷宫的情况 bool vis[1005][1005]; //记录一个点有无被走过 int R,C;初始化函数：
void initialize(){ while(!Joe.empty()) Joe.pop(); while(!fire.empty()) fire.pop(); memset(vis,0,sizeof(vis)); }火的蔓延：
火的蔓延其实也就是向四周搜索一次
这里一个很重要的写法就是先用一个变量x保存当前队列的size，然后让队列中这x个火去蔓延，保证了一次让所有的火只向四周走一步。
其他写法与常规广搜写法并无区别，不做赘述
void fire_spread(){ int x=fire.size(); while(x--){ pos temp=fire.front(); fire.pop(); for(int i=0;i<4;i++){ int xt=temp.x+direct[i][0],yt=temp.y+direct[i][1]; if(xt>=1&&xt<=R&&yt>=1&&yt<=C&&maze[xt][yt]=='.'){ fire.push({xt,yt,temp.step+1}); maze[xt][yt]='F'; } } } }核心代码：
模拟人搜索的过程。
首先函数类型为bool是为了记录最后有没有找到出路。
和火的蔓延一样，为了保证一次走一步，用了x来记录队列当前的size。
注意先让火蔓延，再让人走一步。
bool bfs(){ while(!Joe.empty()){ int x=Joe.size(); fire_spread(); while(x--){ pos temp=Joe.front(); Joe.pop(); if(temp.x==R||temp.x==1||temp.y==C||temp.y==1){ ans=temp.step+1; return 1; } for(int i=0;i<4;i++){ int xt=temp.x+direct[i][0],yt=temp.y+direct[i][1]; if(xt>=1&&xt<=R&&yt>=1&&yt<=C&&maze[xt][yt]=='.'&&!vis[xt][yt]){ vis[xt][yt]=1; maze[xt][yt]='J'; Joe.push({xt,yt,temp.step+1}); } } } } return 0; }AC代码：
#include<string.h> #include<queue> #include<iostream> using namespace std; typedef struct{ int x,y; int step; }pos; int ans; int direct[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; queue<pos>Joe; queue<pos>fire; char maze[1005][1005]; bool vis[1005][1005]; int R,C; void fire_spread(){ int x=fire.size(); while(x--){ pos temp=fire.front(); fire.pop(); for(int i=0;i<4;i++){ int xt=temp.x+direct[i][0],yt=temp.y+direct[i][1]; if(xt>=1&&xt<=R&&yt>=1&&yt<=C&&maze[xt][yt]=='.'){ fire.push({xt,yt,temp.step+1}); maze[xt][yt]='F'; } } } } bool bfs(){ while(!Joe.empty()){ int x=Joe.size(); fire_spread(); while(x--){ pos temp=Joe.front(); Joe.pop(); if(temp.x==R||temp.x==1||temp.y==C||temp.y==1){ ans=temp.step+1; return 1; } for(int i=0;i<4;i++){ int xt=temp.x+direct[i][0],yt=temp.y+direct[i][1]; if(xt>=1&&xt<=R&&yt>=1&&yt<=C&&maze[xt][yt]=='.'&&!vis[xt][yt]){ vis[xt][yt]=1; maze[xt][yt]='J'; Joe.push({xt,yt,temp.step+1}); } } } } return 0; } void initialize(){ while(!Joe.empty()) Joe.pop(); while(!fire.empty()) fire.pop(); memset(vis,0,sizeof(vis)); } int main() { int T; cin>>T; while(T--){ initialize(); cin>>R>>C; for(int i=1;i<=R;i++) for(int j=1;j<=C;j++){ cin>>maze[i][j]; if(maze[i][j]=='J') Joe.push({i,j,0}); else if(maze[i][j]=='F') fire.push({i,j,0}); } if(bfs()) cout<<ans<<endl; else cout<<"IMPOSSIBLE"<<endl; } return 0; }
