首页 > 代码库 > POJ No 3669 Meteor Shower_BFS搜索
POJ No 3669 Meteor Shower_BFS搜索
#include <iostream>#include <cstring>#include <queue>#include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;const int maxn = 500;const int INF = 50000000;int M;struct Meteor { int X, Y; int Time; //Time_i Meteor(int X = 0, int Y = 0, int T = 0) : X(X), Y(Y), Time(T) {} bool operator < (const Meteor& b) { // 升序排序 return Time < b.Time; }} meteor[50000 + 3];int dir[5][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {0, 0}};bool used[maxn][maxn];int field[maxn][maxn]; //标记好每个位置被流星砸(以及扩散到)的时间 int last;int ans; void input();void solve();bool check(int r, int c, int T);int BFS(int r, int c, int T);void input(){ memset(used, false, sizeof(used)); for (int i = 0; i < maxn; i++) { for (int j = 0; j < maxn; j++) { field[i][j] = INF; } } scanf("%d", &M); for (int i = 0; i < M; i++) { scanf("%d%d%d", &meteor[i].X, &meteor[i].Y, &meteor[i].Time); } sort(meteor, meteor + M); //按照时间升序排序 last = meteor[M - 1].Time; //最后被毁灭的时间 for (int i = 0; i < M; i++) //M个火球 { for (int j = 0; j < 5; j++) { //5个方向 int x = meteor[i].X + dir[j][0], y = meteor[i].Y + dir[j][1]; if ( check(x, y, meteor[i].Time) ) { field[x][y] = meteor[i].Time; //x,y位置和周围扩散位置,破坏的时间 } } }}bool check(int r, int c, int T){ return r >= 0 && c >= 0 && field[r][c] > T;}int BFS(int r, int c, int T){ used[r][c] = true; //从原点开始 queue<Meteor> que; Meteor cur; cur.X = r, cur.Y = c, cur.Time = T; que.push(cur); //开始的位置,和时间 while (!que.empty()) { Meteor m = que.front(); que.pop(); for (int i = 0; i < 4; i++) { //遍历4个方向, 因为最后一个方向,是在原地 cur = m; cur.X = m.X + dir[i][0], cur.Y = m.Y + dir[i][1]; //周围位置 cur.Time++; //移到下个位置的时间 //如果火球落到该位置的时间>当前人的时间,表示还有机会移动 if (check(cur.X, cur.Y, cur.Time) && !used[cur.X][cur.Y]) { used[cur.X][cur.Y] = true; //说明当前位置时间永远不会被炸到 //last是最后被炸到的时间 if (field[cur.X][cur.Y] > last) { return cur.Time; //则返回当前到达安全的时间 } que.push(cur); //否则入队列 } } } return -1; //不存在安全位置 }void solve(){ input(); if (field[0][0] == 0) { //原点就被毁灭, 反应时间为0 printf("-1\n"); } else { printf("%d\n", BFS(0, 0, 0)); }}int main(){ solve(); return 0;}
分析:1. 还是经典的BFS问题,主要是要 对被摧毁的位置的时间进行记录(先升序处理)(以及波及到的位置进行时间标志).
2. 人行打算走下一步的时候, 先判断是否时间允许,允许标志为访问过(允许的时候,需要当前位置时间是否已经超过了 最后被毁灭位置的时间,是则返回 到达该安全位置的时间)。不允许则添加到队列中。
题目链接: http://poj.org/problem?id=3669
参考了这篇博客: http://www.cnblogs.com/ZefengYao/p/5935161.html
POJ No 3669 Meteor Shower_BFS搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。