Uvaoj 11624 - Fire!

/*************************************************************************
    > File Name: test.cpp
    > Author: HJZ
    > Mail: 2570230521@qq.com 
    > Created Time: 2014年08月03日 星期日 07时26分58秒
 ************************************************************************/

/*
   题目大意：一个人joe想从迷宫中逃脱，但是迷宫中有着火的地方！joe每分钟向上下左右其中一个方向走一步，当然有火的地方和有墙的地方是不能通过的！
   另外，火的蔓延的方向是同一时刻向上下左右四个方向蔓延！

   思路：每一时刻，先将火的蔓延位置标记出来，并将新的火的位置放入队列qf中；
   因为某一时刻，我们将所有joe可能走的路径都放入了队列中了，假如t1时刻他能走的位置是5个，那么在t1+1时刻，根据上一时刻t1的可能位置更新t1+1
   时刻的可能位置，t1时刻的位置出队列q， t1+1时刻的新位置并重新进入队列！
*/

#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include<cmath>
#include <algorithm>
#include<queue>
#define M 1005
#define mem(a) (memset((a), 0, sizeof(a)))
#define get(s) fgets(s, sizeof(s)-1, stdin)

using namespace std;

char map[M][M];
int n, m;
int bg, ed;
int dir[4][2]={1, 0, 0, 1, -1, 0, 0, -1};

struct Point{
   int x, y, step;
   Point(){
     
   }
   Point(int x, int y, int step){
      this->x=x; 
      this->y=y; 
      this->step=step;
   }
};
queue<Point>q; queue<Point>qf;
int cntF;//某一时刻，火点的位置进入队列的个数
int cntP;//某一时刻，joe可走位置进入队列的个数

int bfs(){
   while(!q.empty()) q.pop();
   q.push(Point(bg, ed, 1));
   while(1){
      while(!qf.empty() && cntF){
         Point  Fcur=qf.front();
         qf.pop();
         --cntF;
         int x=Fcur.x, y=Fcur.y;
         for(int i=0; i<4; ++i){
            int xx=x+dir[i][0];
            int yy=y+dir[i][1];
            if(map[xx][yy]!='F' && map[xx][yy]!='#'){
               map[xx][yy]='F';
               qf.push(Point(xx, yy, 0));
            }
         }
      }
      cntF=qf.size();
      while(!q.empty() && cntP){
            Point cur=q.front();
         q.pop(); --cntP; int x=cur.x, y=cur.y;
        if(x==1 || x==n || y==1 || y==m) return cur.step;
        for(int i=0; i<4; ++i){
          int xx=x+dir[i][1];
          int yy=y+dir[i][0];
          if(map[xx][yy]!='#' && map[xx][yy]!='F' && map[xx][yy]!='X'){
              map[xx][yy]='X'; 
              if(x==1 || x==n || y==1 || y==m) return cur.step+1;
              q.push(Point(xx, yy, cur.step+1)); } } }
          cntP=q.size();
      if(cntP==0)  return -1;
   }
   return -1;
}

int main(){
   int t;
   scanf("%d", &t);
   while(t--){
      scanf("%d%d", &n, &m);
      for(int i=0; i<=n+1; ++i)
         map[i][0]=map[i][m+1]='#';
      for(int i=0; i<=m+1; ++i)
         map[0][i]=map[n+1][i]='#';
      
      while(!qf.empty())  qf.pop();
      cntF=0;
      cntP=1;
          for(int j=0, i=1; i<=n; ++i){
         scanf("%s", map[i]+1);
         for(j=1; j<=m; ++j)
            if(map[i][j]=='J'){
                bg=i;
                ed=j;
            }
            else if(map[i][j]=='F'){
                ++cntF;
                qf.push(Point(i, j, 0));
            }
         map[i][j]='#';
      }     

        int tt=bfs();
        if(tt!=-1)
           printf("%d\n", tt);
        else printf("IMPOSSIBLE\n");
   }
   return 0;
}