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;

}

本文转自小眼儿博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3888581.html，如需转载请自行联系原作者