UVa 11624 Fire

題意：

　　J在一個迷宮裡，迷宮有"不只一個"起火點F，J一分鐘移動一步，而火焰一分鐘也會向上下左右蔓延一步，J只要碰到迷宮的邊緣即可逃走，確認J是否能逃走，如果可以，輸出要走的最短步數。

想法：

　　將每個起火點用vector(或array)存下來，然後同時用兩個BFS，先讓所有起火點先動一步，再讓J動一步，確認J是否能碰到迷宮的邊緣。

　　用int Maze[1001][1001]來描述該迷宮的情況，我用-2代表起火點，-1代表牆壁('#')，0代表可以走的路，用BFS時，每次為了確認火焰都只動一步，因此勢必要記錄火焰走的步數，每次火焰走下一步時Maze[nxt_i][nxt_j] = Maze[cur_i][cur_j] - 1，用負數記錄火焰步數，而正數用來記錄Joe的步數。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;
	int R, C;
	int Maze[1001][1001]; // -2:'F', 0:'.', -1:'#'
	struct point_type{
	int x;
	int y;
	};
	vector<queue<point_type>> QF; // 存每個起火點
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	int BFS(point_type J)
	{
	queue<point_type> QJ; QJ.push(J); // 存Joe
	point_type cur, nxt;
	int minute;
	while(!QJ.empty()) {
	for (int i = 0; i < QF.size(); ++i) { // 多個火焰都要各動一步
	if (!QF[i].empty()){
	cur = QF[i].front();
	minute = Maze[cur.x][cur.y]; // 讓該火焰只動完目前這一分鐘後
	}
	while (!QF[i].empty()){
	cur = QF[i].front();
	if (Maze[cur.x][cur.y] != minute) break; // 就跳出queue 換成 J 移動
	QF[i].pop();
	for (int x = 0; x < 4; ++x) {
	nxt.x = cur.x + direction[x][0];
	nxt.y = cur.y + direction[x][1];
	if (nxt.x < 0 || nxt.x >= R || nxt.y < 0 || nxt.y >= C) continue;
	if (Maze[nxt.x][nxt.y] == 0) {
	Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] - 1;
	QF[i].push(nxt);
	}
	}
	}
	}
	cur = QJ.front();
	minute = Maze[cur.x][cur.y];
	while (!QJ.empty()) {
	cur = QJ.front();
	if (Maze[cur.x][cur.y] != minute) break; //只動完一步後 就換火焰移動
	QJ.pop();
	for (int x = 0; x < 4; ++x) {
	nxt.x = cur.x + direction[x][0];
	nxt.y = cur.y + direction[x][1];
	if (nxt.x < 0 || nxt.x >= R || nxt.y < 0 || nxt.y >= C)
	return Maze[cur.x][cur.y];
	if (Maze[nxt.x][nxt.y] == 0) {
	Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] + 1;
	QJ.push(nxt);
	}
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case;
	char line[1005];
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &R, &C);
	point_type J;
	QF.clear();
	for (int i = 0; i < R; ++i) {
	scanf("%s", line);
	for (int j = 0; j < C; ++j) {
	if (line[j] == '.')
	Maze[i][j] = 0;
	else if (line[j] == '#')
	Maze[i][j] = -1;
	else if (line[j] == 'J') {
	J = {i,j};
	Maze[i][j] = 1;
	}
	else if (line[j] == 'F') {
	queue<point_type> tmp;
	tmp.push({i,j});
	QF.push_back(tmp);
	Maze[i][j] = -2;
	}
	}
	}
	int minute = BFS(J);
	if (minute == -1) puts("IMPOSSIBLE");
	else printf("%d\n", minute);
	}
	return 0;
	}

view raw [UVa] 11624 Fire!.cpp hosted with ❤ by GitHub