POJ 2225 - Asteroids!

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

概要

N * N * N の三次元のマップが与えられ，与えられたスタート地点からゴール地点までの最短距離を答える． ただしゴール地点に辿りつけない場合は「NO ROUTE」と出力する．

制約

• 1 <= N <= 10

解法

BFS するだけ．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 struct triple
 7 {
 8   int i, j, k;
 9   triple() {}
10   triple(int a, int b, int c) : i(a), j(b), k(c) {}
11   bool operator==(const triple& that) const { return i == that.i && j == that.j && k == that.k; }
12 };
13 
14 int bfs(const vector<vector<string> >& cube, const triple& start, const triple& goal)
15 {
16   const int N = cube.size();
17   queue<triple> q;
18   vector<vector<vector<int> > > dist(N, vector<vector<int> >(N, vector<int>(N, 1000000)));
19   dist[start.i][start.j][start.k] = 0;
20   q.push(start);
21   while (!q.empty()) {
22     const triple t = q.front();
23     q.pop();
24     if (t == goal) {
25       return dist[t.i][t.j][t.k];
26     }
27     for (int d = 0; d < 6; d++) {
28       static const int di[] = {-1, 1, 0, 0, 0, 0};
29       static const int dj[] = {0, 0, -1, 1, 0, 0};
30       static const int dk[] = {0, 0, 0, 0, -1, 1};
31       const int i = t.i + di[d];
32       const int j = t.j + dj[d];
33       const int k = t.k + dk[d];
34       if (0 <= i && i < N && 0 <= j && j < N && 0 <= k && k < N && cube[i][j][k] == 'O' && dist[t.i][t.j][t.k]+1 < dist[i][j][k]) {
35         dist[i][j][k] = dist[t.i][t.j][t.k] + 1;
36         q.push(triple(i, j, k));
37       }
38     }
39   }
40   return -1;
41 }
42 
43 int main()
44 {
45   string word;
46   int N;
47   while (cin >> word >> N) {
48     vector<vector<string> > cube(N, vector<string>(N));
49     for (int i = 0; i < N; i++) {
50       for (int j = 0; j < N; j++) {
51         cin >> cube[i][j];
52       }
53     }
54     triple start, goal;
55     cin >> start.k >> start.j >> start.i;
56     cin >> goal.k >> goal.j >> goal.i;
57     cin >> word;
58     const int r = bfs(cube, start, goal);
59     if (r == -1) {
60       cout << "NO ROUTE" << endl;
61     } else {
62       cout << N << ' ' << r << endl;
63     }
64   }
65   return 0;
66 }