首页 > 代码库 > 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搜索