UVA - 11624 - Fire! （BFS的應用）

UVA - 11624 - Fire! （BFS的應用）

A - Fire! Time Limit:1000MS Memory Limit:0KB 64bit IO Format:%lld & %llu SubmitStatus

Description

Problem B: 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.

Given Joe's location in the maze and which squares of the maze are on fire,you must determine whether Joe can exit the maze before the fire reaches him,and how fast he can do it.

Joe and the fire each move one square per minute, vertically or horizontally (notdiagonally). The fire spreads all four directions from each square that is onfire. Joe may exit the maze from any square that borders the edge of the maze.Neither Joe nor the fire may enter a square that is occupied by a wall.

Input Specification

The first line of input contains a single integer, the number of test cases to follow.The first line of each test case contains the two integersR and C, separatedby spaces, with 1 <= R,C <= 1000. The followingR lines of the test caseeach contain one row of the maze. Each of these lines contains exactlyC characters,and each of these characters is one of:

#, a wall., a passable squareJ, Joe's initial position in the maze, which is a passable squareF, a square that is on fire There will be exactly one J in each test case.

Sample Input

2
4 4
####
#JF#
#..#
#..#
3 3
###
#J.
#.F

Output Specification

For each test case, output a single line containing IMPOSSIBLE if Joe cannot exit the maze beforethe fire reaches him, or an integer giving the earliest time Joe can safely exit themaze, in minutes.

Output for Sample Input

3
IMPOSSIBLE
















圖論基礎題。。




AC代碼：

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int maxn = 1010;
int n, m;
char g[maxn][maxn];				//用於存儲整個圖 
queue > q;		//用於bfs的隊列 
int a[maxn][maxn];				//用於存儲每個格子開始起火的時間 
int move[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};		//用於上下左右走 

void bfs1()				//第一次遍歷，預處理每個格子起火的時間 
{
	memset(a, -1, sizeof(a));			//初始化 
	while(!q.empty()) q.pop();			//清空隊列 
	for(int i=0; i tmp = q.front();
		q.pop();
		int x = tmp.first, y = tmp.second;
		for(int i=0; i<4; i++)
		{
			int t1 = x + move[i][0], t2 = y + move[i][1];
			if(a[t1][t2] != -1) continue;
			if(t1 < 0 || t2 < 0 || t1 >= n || t2 >= m) continue;
			if(g[t1][t2] == '#') continue;
			a[t1][t2] = a[x][y] + 1;
			q.push(make_pair(t1, t2));
		}
	}
}

int b[maxn][maxn];
int bfs2()					//第二次遍歷 
{
	memset(b, -1, sizeof(b));
	while(!q.empty()) q.pop();
	for(int i=0; i tmp = q.front();
		q.pop();
		int x = tmp.first, y = tmp.second;
		if(x == 0 || y == 0 ||  x == n - 1 || y == m - 1)
			return b[x][y] + 1;
		for(int i=0; i<4; i++)
		{
			int t1 = x + move[i][0], t2 = y + move[i][1];
			if(t1<0 || t2<0 || t1>=n || t2>=m)continue;
            if(b[t1][t2]!=-1)continue;
            if(g[t1][t2]=='#')continue;
            if(a[t1][t2] != -1 && b[x][y] + 1 >= a[t1][t2]) continue;
            b[t1][t2] = b[x][y] + 1;
            q.push(make_pair(t1, t2));
		}
	}
	return -1;		//沒有路可走出去 
}

int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &n, &m);
		for(int i=0; i