Algoogle

Algorithm for Programming Contest

PKU 3669 Meteor Shower

Category: PKU Tag: bfs

Meteor Shower

問題概要


解法


原点から第1象限をbfsで最短路を出していく.
探索の途中, 各時間でその時間以下の時間に落ちる隕石をすべて落としておく.
bfsが終わっても隕石が残ってたら落とすのを忘れないようにする.

コード


(3669.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int inf = int(1e9);
const int MAX = 310;
const int dx[] = {-1, 1, 0, 0, 0};
const int dy[] = {0, 0, -1, 1, 0};

inline bool in(int x, int y){ return x >= 0 && y >= 0 && x < MAX && y < MAX;}

struct point{
    int x, y, t;
    point(){}
    point(int x, int y, int t):x(x),y(y),t(t){}
    bool operator<(const point &m)const{ return t < m.t;}
};

int M;
int field[MAX][MAX];
point meteor[50010];

int main(){
    scanf("%d", &M);
    for(int i = 0; i < M; i++){
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t);
        meteor[i] = point(x, y, t);
    }
    sort(meteor, meteor+M);
    memset(field, -1, sizeof(field));
    queue<point> bfs;
    int mcnt = 0;
    bfs.push(point(0,0,0));
    while(!bfs.empty()){
        point p = bfs.front(); bfs.pop();
        while(mcnt < M && meteor[mcnt].t <= p.t){
            for(int i = 0; i < 5; i++){
                int nx = meteor[mcnt].x + dx[i], ny = meteor[mcnt].y + dy[i];
                if(in(nx, ny)) field[nx][ny] = inf;
            }
            mcnt++;
        }
        if(field[p.x][p.y] >= 0) continue;
        field[p.x][p.y] = p.t;
        for(int i = 0; i < 4; i++){
            int nx = p.x + dx[i], ny = p.y + dy[i];
            if(in(nx, ny)) bfs.push(point(nx, ny, p.t+1));
        }
    }
    while(mcnt < M){
        for(int i = 0; i < 5; i++){
            int nx = meteor[mcnt].x + dx[i], ny = meteor[mcnt].y + dy[i];
            if(in(nx, ny)) field[nx][ny] = inf;
        }
        mcnt++;
    }
    int ans = inf;
    for(int x = 0; x < MAX; x++)
        for(int y = 0; y < MAX; y++)
            if(field[x][y] >= 0)
                ans = min(ans, field[x][y]);
    if(ans == inf) ans = -1;
    printf("%d\n", ans);
    return 0;
}

Comments