POJ 1522 - N-Credible Mazes

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

概要

\(N\) 次元の点の接続関係とスタート地点とゴール地点が与えられるので、スタート地点からゴール地点まで到達できるかどうかを答える。

制約

• \(1 \le N \le 10\)

解法

BFS するだけ。

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 #include <set>
 5 #include <queue>
 6 using namespace std;
 7 
 8 pair<vector<int>, vector<int> > read(int N)
 9 {
10   vector<int> v[2];
11   for (int i = 0; i < 2; i++) {
12     v[i].resize(N);
13     for (int j = 0; j < N; j++) {
14       cin >> v[i][j];
15     }
16   }
17   return make_pair(v[0], v[1]);
18 }
19 
20 int main()
21 {
22   int N;
23   for (int Ti = 1; cin >> N && N != 0; Ti++) {
24     vector<int> v[2];
25     for (int i = 0; i < 2; i++) {
26       v[i].resize(N);
27       for (int j = 0; j < N; j++) {
28         cin >> v[i][j];
29       }
30     }
31     map<vector<int>, vector<vector<int> > > g;
32     for (int n; cin >> n && n != -1;) {
33       vector<int> a(N), b(N);
34       a[0] = n;
35       for (int i = 1; i < N; i++) {
36         cin >> a[i];
37       }
38       for (int i = 0; i < N; i++) {
39         cin >> b[i];
40       }
41       g[a].push_back(b);
42       g[b].push_back(a);
43     }
44 
45     cout << "Maze #" << Ti << " ";
46     queue<vector<int> > q;
47     set<vector<int> > visited;
48     q.push(v[0]);
49     visited.insert(v[0]);
50     while (!q.empty()) {
51       const vector<int> n = q.front();
52       q.pop();
53       if (n == v[1]) {
54         cout << "can";
55         goto OK;
56       }
57       vector<vector<int> >& es = g[n];
58       for (vector<vector<int> >::const_iterator it = es.begin(); it != es.end(); ++it) {
59         if (!visited.count(*it)) {
60           visited.insert(*it);
61           q.push(*it);
62         }
63       }
64     }
65     cout << "cannot";
66 OK:
67     cout << " be travelled" << endl;
68   }
69   return 0;
70 }