Uvaoj 11624 - Fire!

  1 /*************************************************************************
  2     > File Name: test.cpp
  3     > Author: HJZ
  4     > Mail: 2570230521@qq.com 
  5     > Created Time: 2014年08月03日 星期日 07时26分58秒
  6  ************************************************************************/
  7 
  8 /*
  9    题目大意：一个人joe想从迷宫中逃脱，但是迷宫中有着火的地方！joe每分钟向上下左右其中一个方向走一步，当然有火的地方和有墙的地方是不能通过的！
 10    另外，火的蔓延的方向是同一时刻向上下左右四个方向蔓延！
 11 
 12    思路：每一时刻，先将火的蔓延位置标记出来，并将新的火的位置放入队列qf中；
 13    因为某一时刻，我们将所有joe可能走的路径都放入了队列中了，假如t1时刻他能走的位置是5个，那么在t1+1时刻，根据上一时刻t1的可能位置更新t1+1
 14    时刻的可能位置，t1时刻的位置出队列q， t1+1时刻的新位置并重新进入队列！
 15 */
 16 
 17 #include <queue>
 18 #include <string>
 19 #include <cstdio>
 20 #include <cstring>
 21 #include <iostream>
 22 #include <iomanip>
 23 #include<cmath>
 24 #include <algorithm>
 25 #include<queue>
 26 #define M 1005
 27 #define mem(a) (memset((a), 0, sizeof(a)))
 28 #define get(s) fgets(s, sizeof(s)-1, stdin)
 29 
 30 using namespace std;
 31 
 32 char map[M][M];
 33 int n, m;
 34 int bg, ed;
 35 int dir[4][2]={1, 0, 0, 1, -1, 0, 0, -1};
 36 
 37 struct Point{
 38    int x, y, step;
 39    Point(){
 40      
 41    }
 42    Point(int x, int y, int step){
 43       this->x=x; 
 44       this->y=y; 
 45       this->step=step;
 46    }
 47 };
 48 queue<Point>q; queue<Point>qf;
 49 int cntF;//某一时刻，火点的位置进入队列的个数
 50 int cntP;//某一时刻，joe可走位置进入队列的个数
 51 
 52 int bfs(){
 53    while(!q.empty()) q.pop();
 54    q.push(Point(bg, ed, 1));
 55    while(1){
 56       while(!qf.empty() && cntF){
 57          Point  Fcur=qf.front();
 58          qf.pop();
 59          --cntF;
 60          int x=Fcur.x, y=Fcur.y;
 61          for(int i=0; i<4; ++i){
 62             int xx=x+dir[i][0];
 63             int yy=y+dir[i][1];
 64             if(map[xx][yy]!='F' && map[xx][yy]!='#'){
 65                map[xx][yy]='F';
 66                qf.push(Point(xx, yy, 0));
 67             }
 68          }
 69       }
 70       cntF=qf.size();
 71       while(!q.empty() && cntP){
 72             Point cur=q.front();
 73          q.pop(); --cntP; int x=cur.x, y=cur.y;
 74         if(x==1 || x==n || y==1 || y==m) return cur.step;
 75         for(int i=0; i<4; ++i){
 76           int xx=x+dir[i][1];
 77           int yy=y+dir[i][0];
 78           if(map[xx][yy]!='#' && map[xx][yy]!='F' && map[xx][yy]!='X'){
 79               map[xx][yy]='X'; 
 80               if(x==1 || x==n || y==1 || y==m) return cur.step+1;
 81               q.push(Point(xx, yy, cur.step+1)); } } }
 82           cntP=q.size();
 83       if(cntP==0)  return -1;
 84    }
 85    return -1;
 86 }
 87 
 88 int main(){
 89    int t;
 90    scanf("%d", &t);
 91    while(t--){
 92       scanf("%d%d", &n, &m);
 93       for(int i=0; i<=n+1; ++i)
 94          map[i][0]=map[i][m+1]='#';
 95       for(int i=0; i<=m+1; ++i)
 96          map[0][i]=map[n+1][i]='#';
 97       
 98       while(!qf.empty())  qf.pop();
 99       cntF=0;
100       cntP=1;
101           for(int j=0, i=1; i<=n; ++i){
102          scanf("%s", map[i]+1);
103          for(j=1; j<=m; ++j)
104             if(map[i][j]=='J'){
105                 bg=i;
106                 ed=j;
107             }
108             else if(map[i][j]=='F'){
109                 ++cntF;
110                 qf.push(Point(i, j, 0));
111             }
112          map[i][j]='#';
113       }     
114 
115         int tt=bfs();
116         if(tt!=-1)
117            printf("%d\n", tt);
118         else printf("IMPOSSIBLE\n");
119    }
120    return 0;
121 }