2.1 最基础的“穷竭搜索” 广度优先搜索
有个小文青去看流星雨,不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同,求小文青能否活命,如果能活命,最短的逃跑时间是多少?
思路:对流星雨排序,然后将地图的每个点的值设为该点最早被炸毁的时间。如果起点一开始就被炸毁了的话,那小文青就直接洗剪吹,否则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版)》练习题答案
如果直接找出流星的最晚落下时间,是否可以省去排序?
可以,我这么写比较方便
WA了半天终于过了,94MS,超时的原因是因为cin和cout吧,用printf快很多
stream IO可以加速的http://www.hankcs.com/program/cpp/cin-tie-with-sync_with_stdio-acceleration-input-and-output.html
“”// 一个点只能访问一次,下次就被炸毁了“
应该不是下次就炸毁了吧?这取决于这个点炸毁的时间啊,不访问这个点的原因应该是避免再把这个点放到队列里产生死循环吧?
对,我这么说的确有问题。