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 J ...
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 exactlyC 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.
Sample Input
2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F
Sample Output
3
IMPOSSIBLE
題意：題目：一個平面迷宮中有一個人，迷宮中有些點起火了，火和人每個單位時間只能向相鄰的格子移動， 其中有一些空間被牆壁占據，問這個人在不被燒到的情況下，離開迷宮的最快時
思路：明顯是一個搜索題，但是怎麼搜呢？可以先把所有的格子都掃一遍，然後把帶火的先放到隊列裡面，最後再把J放進隊列，這樣就可以保證在同一秒的時候是火先蔓延了，之後人才再可以走的地方走路，在火蔓延的時候記得把火的性質傳遞過去，我是用了一個id，id為0表示是火，那麼火蔓延的時候把id給傳下去就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<set> #include<vector> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-10 #define PI acos(-1.0) #define _e exp(1.0) #define ll long long int const maxn = 1005; const int mod = 1e9 + 7; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } struct node { int x,y,t,id; }; int n,m,ans,sum; int vis[maxn][maxn]; char map[maxn][maxn]; queue<node>que; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; bool judge(int x,int y) { if(x>=0 && x<n && y>=0 && y<m && !vis[x][y]) //如果在地圖中並且沒有被走過就返回true，我把'#'也當作走過了就不需要判斷#了 return true; return false; } int bfs() { node next; while(!que.empty()) { node p=que.front(); que.pop(); for(int i=0;i<4;i++) { next.x=p.x+dx[i]; next.y=p.y+dy[i]; next.t=p.t+1; next.id=p.id; //把火和沒有火的的性質蔓延下去 if(next.id==1 && (next.x==-1 || next.x==n || next.y==-1 || next.y==m)) //如果到了邊界並且id還是1表示沒有被燒過就可以返回時間t了 return next.t; if(judge(next.x,next.y)) { vis[next.x][next.y]=1; que.push(next); } } } return -1; } int main() { int t; scanf("%d",&t); while(t--) { node s1,s2; scanf("%d%d",&n,&m); while(!que.empty()) que.pop(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { cin>>map[i][j]; if(map[i][j]=='.') vis[i][j]=0; else if(map[i][j]=='#') vis[i][j]=1; else if(map[i][j]=='F') //記錄這是一個火，id為0表示這是一個火 { vis[i][j]=1; s1.x=i; s1.y=j; s1.t=0; s1.id=0; que.push(s1); } else if(map[i][j]=='J') { vis[i][j]=1; s2.x=i; s2.y=j; s2.t=0; s2.id=1; } } } que.push(s2); //先把所有的火都push進去再push人，可以保證在同一秒的時候是火先走，那人只能走不是火的地方，不然就火就和人相遇了 int ans=bfs(); if(ans==-1) puts("IMPOSSIBLE"); else printf("%d\n",ans); } return 0; }
