POJ-3669-流星雨

这题的话，卡了有两个小时左右，首先更新地图的时候越界了，我们进行更新的时候，要判断一下是不是小于零了，越界就会Runtime Error。

然后bfs 的时候，我没有允许它搜出300以外的范围，然后就在300以内搜，然后就错了，实际上题目的意思是流星雨的轰炸范围是0~300，然后我就把世界理解成了300，哼，英文很烂，难受。

所以地图开的大一点，然后直接搜就可以了，这题的思路还是好想的。

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int INF = 0x3f3f3f3f;

int map[305][305];

int vis[305][305];

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

int m;

struct Step {

    int x, y, t;

    Step(int a,int b,int c):x(a),y(b),t(c){}

};

int bfs()

{

    if (!map[0][0])

        return INF;

    vis[0][0] = 1;

    queue<Step> q;

    q.push(Step(0, 0, 0));

    while (!q.empty()) {

        Step now = q.front();

        if (map[now.x][now.y]==INF)

            return now.t;

        for (int i = 1; i < 5;i++) {

            int dx = now.x + d[i][0];

            int dy = now.y + d[i][1];

            if (dx>=0&&dy>=0&&map[dx][dy]>now.t+1&&!vis[dx][dy]) {

                vis[dx][dy]=1;

                q.push(Step(dx, dy, now.t + 1));

            }

        }

        q.pop();

    }

    return INF;

}

int main()

{

    int x, y, t;

    while (scanf("%d",&m)!=EOF) {

        memset(map, INF, sizeof(map));

        memset(vis, 0, sizeof(vis));

        while (m--) {

            scanf("%d%d%d", &x, &y, &t);

            for (int i = 0; i < 5;i++) {

                int dx = x + d[i][0];

                int dy = y + d[i][1];

                if (dx>=0&&dy>=0&&t<map[dx][dy]) {

                	map[dx][dy]=t;

				}

            }

        }

        int min=bfs();

        printf("%d\n", min == INF ? -1 : min);

    }

    return 0;

}

巴特西

POJ-3669-流星雨

最新文章

热门文章