POJ 3501 - Escape from Enemy Territory

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

概要

X * Y のグリッド上に N 個敵の基地がある． 与えられたスタート地点から，なるべく敵基地から遠い所を通って集合場所へ行きたい． 基地とプレイヤーの距離はマンハッタン距離で定める．

プレイヤーは隣接する4マスに1ステップで移動できる．

スタート地点から集合場所まで進んだとき，その経路上における敵基地との距離の最小値の最大値と，そのときの最小のステップ数を答える．

制約

解法

経路上における基地との距離の最小値 D に関して二分探索．

その最小値 D で集合場所へ行けるかどうかは BFS で判定できる．

各マスについて，最も近い敵基地までのマンハッタン距離を予め計算しておくことになるが，このとき愚直に計算すると O(N*X*Y) となって無理． そこで基地を始点として BFS することでこれを計算した．

 1 #include <cstdio>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 static const int M = 1000;
 6 static const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
 7 
 8 int bfs(const int enemies[M][M], int X, int Y, const pair<int,int>& start, const pair<int,int>& goal, int D)
 9 {
10   if (enemies[start.first][start.second] < D) {
11     return -1;
12   }
13   queue<pair<int,int> > q;
14   q.push(start);
15   static int dist[M][M];
16   for (int i = 0; i < X; i++) {
17     fill_n(dist[i], Y, 10000000);
18   }
19   dist[start.first][start.second] = 0;
20   while (!q.empty()) {
21     const int i = q.front().first;
22     const int j = q.front().second;
23     q.pop();
24     for (int d = 0; d < 4; d++) {
25       const int k = i + dx[d], l = j + dy[d];
26       if (0 <= k && k < X && 0 <= l && l < Y && dist[i][j]+1 < dist[k][l] && enemies[k][l] >= D) {
27         dist[k][l] = dist[i][j]+1;
28         pair<int,int> p(k, l);
29         if (p == goal) {
30           return dist[k][l];
31         }
32         q.push(p);
33       }
34     }
35   }
36   return -1;
37 }
38 
39 int main()
40 {
41   int T;
42   scanf("%d", &T);
43   while (T-- > 0) {
44     int N, X, Y;
45     scanf("%d %d %d", &N, &X, &Y);
46     pair<int,int> start, goal;
47     scanf("%d %d %d %d", &start.first, &start.second, &goal.first, &goal.second);
48     static int enemies[M][M];
49     for (int i = 0; i < X; i++) {
50       fill_n(enemies[i], Y, 10000000);
51     }
52     queue<pair<int,int> > q;
53     for (int i = 0; i < N; i++) {
54       int x, y;
55       scanf("%d %d", &x, &y);
56       enemies[x][y] = 0;
57       q.push(make_pair(x, y));
58     }
59     while (!q.empty()) {
60       const int i = q.front().first;
61       const int j = q.front().second;
62       q.pop();
63       for (int d = 0; d < 4; d++) {
64         const int k = i + dx[d], l = j + dy[d];
65         if (0 <= k && k < X && 0 <= l && l < Y && enemies[i][j]+1 < enemies[k][l]) {
66           enemies[k][l] = enemies[i][j]+1;
67           q.push(make_pair(k, l));
68         }
69       }
70     }
71 
72     int left = 0, right = X+Y;
73     int ans = -1, dist = -1;
74     while (left < right) {
75       const int mid = (left + right)/2;
76       const int d = bfs(enemies, X, Y, start, goal, mid);
77       if (d != -1) {
78         ans = mid;
79         dist = d;
80         left = mid+1;
81       } else {
82         right = mid;
83       }
84     }
85     printf("%d %d\n", ans, dist);
86   }
87   return 0;
88 }
poj/3501.cc