uva 11624 Fire!(bfs前処理)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=116#problem/A
标题:joeを助けて大火が広がる迷路を出て、彼は毎分左右の4つの方向の1つを歩くことができて、すべての火事の格子は周りに広がります.joeも火も障害格に入れない.joeが迷宮の境界格子に着いたとき、私たちは彼が迷宮を出たと思っていた.joeが迷宮を出た最小時間を出力し、出られなければ「IMPOSIBLE」を出力した.
構想:bfsを2回.火は消せないので、ある格子がいつか火をつけたら、これからずっと火をつけます.そこで,bfsを用いて各格子が着火した時刻を処理した.2回目のbfsではjoeがその格子に到達する時間がその格子が着火する時間より小さいかどうかを判断するだけでよい.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#define LL long long
#define _LL __int64

using namespace std;
const int maxn = 1010;
const int INF = 0x3f3f3f3f;
struct node
{
	int x,y;
	int step;
};
queue <node> que;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int jx,jy;
char map[maxn][maxn],s[maxn];
int time[maxn][maxn],vis[maxn][maxn];
int n,m;
int ans;

//       （     ）     
void solve()
{
	memset(vis,0,sizeof(vis));
	memset(time,INF,sizeof(time));
	while(!que.empty()) que.pop();

	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
			if(map[i][j] == 'F')
			{
				que.push((struct node){i,j,1});
				time[i][j] = 1;
				vis[i][j] = 1;
			}
	}

	while(!que.empty())
	{
		struct node u = que.front();
		que.pop();

		for(int d = 0; d < 4; d++)
		{
			int x = u.x + dir[d][0];
			int y = u.y + dir[d][1];
			if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#' && !vis[x][y])
			{
				vis[x][y] = 1;
				que.push((struct node){x,y,u.step+1});
				time[x][y] = u.step+1;
			}
		}
	}
}

//  joe       
bool bfs()
{
	memset(vis,0,sizeof(vis));
	while(!que.empty()) que.pop();

	vis[jx][jy] = 1;
	que.push((struct node){jx,jy,1});

	while(!que.empty())
	{
		struct node u = que.front();
		que.pop();

		if(u.x == 1 || u.x == n || u.y == 1 || u.y == m)
		{
			ans = u.step;
			return true;
		}

		for(int d = 0; d < 4; d++)
		{
			int x = u.x + dir[d][0];
			int y = u.y + dir[d][1];
			if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#' && !vis[x][y])
			{
				if(u.step + 1 < time[x][y]) //             
				{
					time[x][y] = 1;
					que.push((struct node){x,y,u.step+1});
				}
			}
		}
	}
	return false;
}

int main()
{
	int test;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d %d",&n,&m);
		for(int i = 1; i <= n; i++)
		{
			scanf("%s",map[i]+1);
			for(int j = 1; j <= m; j++)
				if(map[i][j] == 'J')
				{
					jx = i;
					jy = j;
				}
		}

		solve();
		if(bfs())
			printf("%d
",ans);
		else printf("IMPOSSIBLE
");

	}
	return 0;
}