POJ 3669 - Meteor Shower

http://poj.org/problem?id=3669

概要

M 個の隕石がそれぞれ座標 (X[i], Y[i]) に時刻 T[i] に落ちてくる． 隕石が落ちた座標とその隣接する4つの座標は，時刻 T[i] 以降に進むことはできない．

最初 (0,0) の位置に，単位時間あたりに1マス分進むことができる． その人が安全な位置まで移動するのにかかる時間を答える．

ただし，移動できない場合は -1 を答える．

制約

解法

BFS． 時刻 0 に原点にいられないときも -1 と答えることに注意．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 static const int N = 310;
 8 static const int INF = 10000000;
 9 static int grid[N][N];
10 
11 int solve()
12 {
13   if (grid[1][1] == 0) {
14     return -1;
15   }
16 
17   static int dist[N][N];
18   for (int i = 0; i < N; i++) {
19     fill_n(dist[i], N, INF);
20   }
21   queue<pair<int,int> > q;
22   q.push(make_pair(1, 1));
23   dist[1][1] = 0;
24 
25   while (!q.empty()) {
26     const int x = q.front().first;
27     const int y = q.front().second;
28     q.pop();
29     if (grid[x][y] == INF) {
30       return dist[x][y];
31     }
32     for (int d = 0; d < 4; d++) {
33       static const int dx[] = {-1, 1, 0, 0};
34       static const int dy[] = {0, 0, -1, 1};
35       const int k = x + dx[d];
36       const int l = y + dy[d];
37       const int dd = dist[x][y]+1;
38       if (1 <= k && 1 <= l) {
39         if (dd < grid[k][l] && dd < dist[k][l]) {
40           dist[k][l] = dd;
41           q.push(make_pair(k, l));
42         }
43       }
44     }
45   }
46   return -1;
47 }
48 
49 int main()
50 {
51   for (int i = 0; i < N; i++) {
52     fill_n(grid[i], N, INF);
53   }
54 
55   int M;
56   scanf("%d", &M);
57   for (int i = 0; i < M; i++) {
58     int X, Y, T;
59     scanf("%d %d %d", &X, &Y, &T);
60     ++X;  ++Y;
61     for (int d = 0; d < 5; d++) {
62       static const int dx[] = {0, -1, 1, 0, 0};
63       static const int dy[] = {0, 0, 0, -1, 1};
64       int& g = grid[X+dx[d]][Y+dy[d]];
65       g = min(g, T);
66     }
67   }
68 
69   printf("%d\n", solve());
70   return 0;
71 }
poj/3669.cc