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- 

 this- 

 this- step=step;

queue Point queue Point 

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 ++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 ++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", 

 while(t--){

 scanf("%d%d", n, 

 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 ++i){

 scanf("%s", map[i]+1);

 for(j=1; j ++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;

}

Fire!! 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.