POJ 3346 - Treasure of the Chimp Island

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

概要

\(W \times H\) の迷路が与えられる。 この中に1箇所にだけ宝がある。 迷路の外側は壁か入口に囲まれている。 入口は複数あり、各入口にはダイナマイトが0個から26個置いてあり、スタートした入口のダイナマイトを持って行くことができる。 迷路の中には岩があり、それを壊すのに必要なコストが設定されている。 岩が無い通路はコスト無しで進むことができる。 ダイナマイトを持っている場合、それを1つ消費してどんな岩でも1つコスト無しで壊して通ることができる。

このとき、最適な入口からスタートして宝の場所まで行くのに必要な最小のコストを答える。 ただし、宝へ辿り着けない場合は「IMPOSSIBLE」と答える。

制約

解法

\(H \times W \times 27\) の拡張ダイクストラ。 俺はゴールから逆走するように実装したけど、別に各入口を最初に priority_queue に入れて普通にゴールまで進んでもいける。

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct state
 8 {
 9   int i, j, c, d;
10   state(int x, int y, int z, int w) : i(x), j(y), c(z), d(w) {}
11   bool operator<(const state& s) const { return d > s.d; }
12 };
13 
14 int main()
15 {
16   ios::sync_with_stdio(false);
17   string line;
18   while (getline(cin, line) && line != "--") {
19     vector<string> grid;
20     grid.push_back(line);
21     while (getline(cin, line) && !line.empty()) {
22       grid.push_back(line);
23     }
24 
25     const int H = grid.size(), W = grid[0].size();
26     static const int INF = 10000000;
27     vector<vector<vector<int> > > dist(H, vector<vector<int> >(W, vector<int>(27, INF)));
28     priority_queue<state> q;
29     for (int i = 0; i < H; i++) {
30       for (int j = 0; j < W; j++) {
31         if (grid[i][j] == '$') {
32           q.push(state(i, j, 26, 0));
33           dist[i][j][26] = 0;
34           break;
35         }
36       }
37     }
38 
39     int ans = INF;
40     while (!q.empty()) {
41       const state s = q.top();
42       q.pop();
43       const int d = dist[s.i][s.j][s.c];
44       if (d < s.d) {
45         continue;
46       }
47       const char here = grid[s.i][s.j];
48       if (here == '#') {
49         if (s.c == 26) {
50           ans = min(ans, d);
51         }
52         continue;
53       } else if ('A' <= here && here <= 'Z') {
54         if (here-'A'+1 >= 26-s.c) {
55           ans = min(ans, d);
56         }
57         continue;
58       }
59 
60       for (int k = 0; k < 4; k++) {
61         static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
62         const int i = s.i + di[k], j = s.j + dj[k];
63         if ('1' <= grid[i][j] && grid[i][j] <= '9') {
64           // w/ dynamite
65           if (s.c > 0) {
66             if (d < dist[i][j][s.c-1]) {
67               dist[i][j][s.c-1] = d;
68               q.push(state(i, j, s.c-1, d));
69             }
70           }
71 
72           // w/o dynamite
73           const int dd = d + grid[i][j]-'0';
74           if (dd < dist[i][j][s.c]) {
75             dist[i][j][s.c] = dd;
76             q.push(state(i, j, s.c, dd));
77           }
78         } else if (grid[i][j] != '*') {
79           if (d < dist[i][j][s.c]) {
80             dist[i][j][s.c] = d;
81             q.push(state(i, j, s.c, d));
82           }
83         }
84       }
85     }
86 
87     if (ans == INF) {
88       cout << "IMPOSSIBLE" << endl;
89     } else {
90       cout << ans << endl;
91     }
92   }
93   return 0;
94 }
poj/3346.cc