放牧代码和思想
专注自然语言处理、机器学习算法

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

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

POJ 3669 Meteor Shower

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

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

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

12479151 hankcs 3669 Time Limit Exceeded G++ 2189B
12479154 hankcs 3669 Accepted 2120K 547MS C++ 2189B
#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版)》练习题答案

分享到:更多 ()

评论 8

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    如果直接找出流星的最晚落下时间,是否可以省去排序?

    奥特曼3年前 (2015-02-21)回复
  2. #1

    “”// 一个点只能访问一次,下次就被炸毁了“
    应该不是下次就炸毁了吧?这取决于这个点炸毁的时间啊,不访问这个点的原因应该是避免再把这个点放到队列里产生死循环吧?

    仕成3年前 (2014-08-10)回复
    • 对,我这么说的确有问题。

      hankcs3年前 (2014-08-10)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机