POJ 3170 - Knights of Ni

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

概要

W * H のグリッドが与えられ，各マスの数は

• 0 は通れるマス
• 1 は通れないマス
• 2 はスタート地点 (自由に通れる)
• 3 はゴール地点 (shrubbery を持っていないと通れない)
• 4 は shrubbery (自由に通れる)

を表している．

スタート地点から shrubbery を1つ以上とってゴール地点へ行くときの最小のステップ数を答える．

制約

• 1 <= W, H <= 1000
• ゴールできることは保証されている

解法

• スタート地点から各 shrubbery
• ゴール地点から各 shrubbery

と2回 BFS して，各 shrubbery のマスについてその2つの距離の和の最小値をとればいい．

 1 #include <cstdio>
 2 #include <queue>
 3 using namespace std;
 4 static const int INF = 10000000;
 5 
 6 int W, H;
 7 int grid[1000][1000];
 8 
 9 void bfs(queue<pair<int,int> > q, int dist[1000][1000])
10 {
11   while (!q.empty()) {
12     const int i = q.front().first;
13     const int j = q.front().second;
14     q.pop();
15     if (grid[i][j] == 4) {
16       continue;
17     }
18     for (int d = 0; d < 4; d++) {
19       static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
20       const int k = i + di[d];
21       const int l = j + dj[d];
22       if (0 <= k && k < H && 0 <= l && l < W
23           && (grid[k][l] != 1 && grid[k][l] != 3)
24           && dist[i][j]+1 < dist[k][l]) {
25         dist[k][l] = dist[i][j] + 1;
26         q.push(make_pair(k, l));
27       }
28     }
29   }
30 }
31 
32 int main()
33 {
34   scanf("%d %d", &W, &H);
35   queue<pair<int,int> > q, qq;
36   static int d[1000][1000], dd[1000][1000];
37   for (int i = 0; i < H; i++) {
38     for (int j = 0; j < W; j++) {
39       scanf("%d", &grid[i][j]);
40       if (grid[i][j] == 2) {
41         q.push(make_pair(i, j));
42         d[i][j] = 0;
43       } else {
44         d[i][j] = INF;
45       }
46       if (grid[i][j] == 3) {
47         qq.push(make_pair(i, j));
48         dd[i][j] = 0;
49       } else {
50         dd[i][j] = INF;
51       }
52     }
53   }
54   bfs(q, d);
55   bfs(qq, dd);
56   int ans = INF;
57   for (int i = 0; i < H; i++) {
58     for (int j = 0; j < W; j++) {
59       if (grid[i][j] == 4) {
60         ans = min(ans, d[i][j] + dd[i][j]);
61       }
62     }
63   }
64   printf("%d\n", ans);
65   return 0;
66 }