Uvaoj 11624 - Fire!

/*************************************************************************

    > File Name: test.cpp

    > Author: HJZ

    > Mail: [email protected] 

    > 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;

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/3888581.html，如需轉載請自行聯系原作者