POJ 2435 - Navigating the City

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

概要

N * E の地図とスタート地点・ゴール地点が与えられるので，その最短距離とそのときの経路を答える．

制約

• 1 <= E <= 40
• 1 <= N <= 30

解法

BFS するだけ．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <queue>
 5 using namespace std;
 6 
 7 int main()
 8 {
 9   int H, W;
10   cin >> H >> W;
11   vector<string> grid(2*H+3, string(2*W+3, '.'));
12   queue<pair<int,int> > q;
13   static const int INF = 10000000;
14   vector<vector<int> > dist(2*H+3, vector<int>(2*W+3, INF));
15   vector<vector<int> > prev(2*H+3, vector<int>(2*W+3, -1));
16   vector<vector<int> > prev_step(2*H+3, vector<int>(2*W+3, -1));
17   for (int i = 1; i <= 2*H; i++) {
18     string line;
19     cin >> line;
20     grid[i] = "." + line + ".";
21     for (int j = 1; j <= 2*W; j++) {
22       if (grid[i][j] == 'S') {
23         q.push(make_pair(i, j));
24         dist[i][j] = 0;
25       }
26     }
27   }
28 
29   static const int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
30   static const char tbl[] = "NSWE";
31   while (!q.empty()) {
32     const int i = q.front().first;
33     const int j = q.front().second;
34     q.pop();
35     if (grid[i][j] == 'E') {
36       // print
37       vector<string> output;
38       int k = i, l = j;
39       while (dist[k][l] > 0) {
40         ostringstream oss;
41         oss << tbl[prev[k][l]] << ' ' << prev_step[k][l];
42         output.push_back(oss.str());
43         int next_k = k - di[prev[k][l]] * (prev_step[k][l]*2);
44         int next_l = l - dj[prev[k][l]] * (prev_step[k][l]*2);
45         k = next_k;
46         l = next_l;
47       }
48       for (vector<string>::const_reverse_iterator it = output.rbegin(); it != output.rend(); ++it) {
49         cout << *it << endl;
50       }
51       break;
52     }
53 
54     for (int d = 0; d < 4; d++) {
55       int k = i, l = j;
56       int step = 0;
57       while (true) {
58         k += di[d];
59         l += dj[d];
60         if (grid[k][l] == '.') {
61           break;
62         }
63         k += di[d];
64         l += dj[d];
65         ++step;
66         if (dist[i][j]+step < dist[k][l]) {
67           dist[k][l] = dist[i][j]+step;
68           prev[k][l] = d;
69           prev_step[k][l] = step;
70           q.push(make_pair(k, l));
71         }
72       }
73     }
74   }
75   return 0;
76 }