POJ 3669 Meteor Shower 《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 广度优先搜索

POJ 3669 Meteor Shower

有个小文青去看流星雨，不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同，求小文青能否活命，如果能活命，最短的逃跑时间是多少？

思路：对流星雨排序，然后将地图的每个点的值设为该点最早被炸毁的时间。如果起点一开始就被炸毁了的话，那小文青就直接洗剪吹，否则bfs。

吐个槽，同一段代码用G++提交TLE，用C++提交AC，没想明白为什么。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;

#define INDEX_MAX 512
int map[INDEX_MAX][INDEX_MAX];
bool visited[INDEX_MAX][INDEX_MAX];
struct Meteor
{
	int x, y, t;
};
typedef Meteor P;

Meteor m[50008];
int n;

const int direction[5][2] = {
	{ -1, 0 },
	{ 1, 0 },
	{ 0, -1 },
	{ 0, 1 },
	{ 0, 0 },
};

int last;

int bfs()
{
	memset(visited, 0, sizeof(visited));
	queue<P> que;
	P current;
	current.x = 0;
	current.y = 0;
	// 当前花费时间
	current.t = 0;
	que.push(current);
	while (que.size())
	{
		// 做个备份
		const P p = que.front(); que.pop();
		for (int j = 0; j < 4; ++j)
		{
			current = p;
			current.x = current.x + direction[j][0];
			current.y = current.y + direction[j][1];
			++current.t;
			
			if (current.x >= 0 && current.y >= 0 && map[current.x][current.y] > current.t && !visited[current.x][current.y])
			{
				visited[current.x][current.y] = true;
				// 爆炸时间大于当前时间，是安全的
				if (map[current.x][current.y] > last)
				{
					// 当前位置爆炸时间大于流星雨最晚落下的时间，说明跑出了流星雨区域
					return current.t;
				}
				que.push(current);
			}
		}
	}

	return -1;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> m[i].x >> m[i].y >> m[i].t;
	}
	
	// 地图中每个点的值表示最早在什么时候被炸毁
	memset(map, 0x7F, sizeof(map));
	for (int i = 0; i < n; ++i)
	{
		last = max(last, m[i].t);
		for (int j = 0; j < 5; ++j)
		{
			int nx = m[i].x + direction[j][0];
			int ny = m[i].y + direction[j][1];
			if (nx >= 0 && ny >= 0 && map[nx][ny] > m[i].t)
			{
				map[nx][ny] = m[i].t;
			}
		}
	}
	if (map[0][0] == 0)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << bfs() << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3669 Meteor Shower 《挑战程序设计竞赛(第2版)》练习题答案