POJ 2312 - Battle City

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

概要

M * N のグリッド上で，スタート地点からゴール地点までの最小のステップ数を答える．

各マスは

のいずれか．

1ステップで

のどちらかの行動ができる．

制約

解法

れんがの壁は，そのマスを通る直前に壊すことにすれば，B を通るときに2ステップかかると見なしてよい．

よって，単にダイクストラするだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   int M, N;
 9   while (cin >> M >> N && M != 0) {
10     vector<string> grid(M);
11     pair<int,int> start, goal;
12     for (int i = 0; i < M; i++) {
13       cin >> grid[i];
14       for (int j = 0; j < N; j++) {
15         if (grid[i][j] == 'Y') {
16           start = make_pair(i, j);
17           grid[i][j] = 'E';
18         } else if (grid[i][j] == 'T') {
19           goal = make_pair(i, j);
20           grid[i][j] = 'E';
21         }
22       }
23     }
24 
25     priority_queue<pair<int, pair<int,int> > > q;
26     static const int INF = 10000000;
27     vector<vector<int> > dist(M, vector<int>(N, INF));
28     q.push(make_pair(0, start));
29     dist[start.first][start.second] = 0;
30     while (!q.empty() && q.top().second != goal) {
31       const int c = -q.top().first;
32       const int i = q.top().second.first;
33       const int j = q.top().second.second;
34       q.pop();
35       if (c > dist[i][j]) {
36         continue;
37       }
38       for (int d = 0; d < 4; d++) {
39         static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
40         const int k = i + di[d], l = j + dj[d];
41         if (0 <= k && k < M && 0 <= l && l < N && grid[k][l] != 'R' && grid[k][l] != 'S') {
42           const int cc = dist[i][j] + (grid[k][l] == 'B' ? 2 : 1);
43           if (cc < dist[k][l]) {
44             dist[k][l] = cc;
45             q.push(make_pair(-cc, make_pair(k, l)));
46           }
47         }
48       }
49     }
50 
51     if (dist[goal.first][goal.second] == INF) {
52       cout << "-1" << endl;
53     } else {
54       cout << dist[goal.first][goal.second] << endl;
55     }
56   }
57   return 0;
58 }
poj/2312.cc