POJ 1137 - The New Villa

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

概要

r 個の部屋をもつ別荘がある．1番目の部屋が玄関で，r 番目の部屋が寝室．各部屋には明かりがある． d 個の廊下があり，それぞれ1つの部屋と1つの部屋を繋いでいる． s 個のスイッチがあり，各スイッチはいずれかの部屋に存在し，いずれかの部屋の明かりを点けたり消したりできる．

今，玄関のみ明かりが点いており，自分も玄関にいる． スイッチを押したり，廊下を渡って明かりの点いている部屋に移動したりしながら，最終的に寝室に行き，寝室のみ明かりが点いている状態にしたい． 最小のステップ数でそのような状態するとき，どのように行動すればいいかを答える．

ただし，1ステップは

のいずれかに対応する．

制約

解法

状態数は r * 2^r 程度なので，これで単に BFS すればいい．

しかし，同じ最小のステップ数にする行動の仕方は一通りとは限らないのに，どれを出力すればよいか示されていないし Special Judge でもない糞ゲー．

みたいにしたら通った．

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 int main()
 9 {
10   int R, D, S;
11   for (int Ti = 1; cin >> R >> D >> S && R != 0; Ti++) {
12     vector<vector<int> > g(R);
13     for (int i = 0; i < D; i++) {
14       int u, v;
15       cin >> u >> v;
16       --u;  --v;
17       g[u].push_back(v);
18       g[v].push_back(u);
19     }
20     vector<vector<int> > switches(R);
21     for (int i = 0; i < S; i++) {
22       int u, v;
23       cin >> u >> v;
24       --u;  --v;
25       if (u != v) {
26         switches[u].push_back(v);
27       }
28     }
29     for (int i = 0; i < R; i++) {
30       sort(switches[i].begin(), switches[i].end());
31     }
32 
33     queue<pair<int,int> > q;
34     q.push(make_pair(0, 1));
35     vector<vector<int> > dist(R, vector<int>(1<<R, 1000000));
36     vector<vector<pair<bool,int> > > prev(R, vector<pair<bool,int> >(1<<R));
37     dist[0][1] = 0;
38     cout << "Villa #" << Ti << endl;
39     while (!q.empty()) {
40       int n = q.front().first;
41       int s = q.front().second;
42       q.pop();
43       const int d = dist[n][s];
44       if (n == R-1 && s == (1<<(R-1))) {
45         cout << "The problem can be solved in " << d << " steps:" << endl;
46         vector<string> msg;
47         for (int i = 0; i < d; i++) {
48           ostringstream oss;
49           const int j = prev[n][s].second;
50           if (prev[n][s].first) {
51             // switch
52             oss << "- Switch " << (s & (1<<j) ? "on" : "off") << " light in room " << j+1 << ".";
53             s ^= (1<<j);
54           } else {
55             // move
56             oss << "- Move to room " << n+1 << ".";
57             n = j;
58           }
59           msg.push_back(oss.str());
60         }
61         for (vector<string>::reverse_iterator it = msg.rbegin(); it != msg.rend(); ++it) {
62           cout << *it << endl;
63         }
64         goto NEXT;
65       }
66       // goto next room
67       for (vector<int>::const_iterator it(g[n].begin()); it != g[n].end(); ++it) {
68         if (s & (1<<*it) && d+1 < dist[*it][s]) {
69           dist[*it][s] = d+1;
70           prev[*it][s].first = false;
71           prev[*it][s].second = n;
72           q.push(make_pair(*it, s));
73         }
74       }
75       // turn switch
76       for (vector<int>::const_iterator it(switches[n].begin()); it != switches[n].end(); ++it) {
77         const int t = s ^ (1<<*it);
78         if (d+1 < dist[n][t]) {
79           dist[n][t] = d+1;
80           prev[n][t].first = true;
81           prev[n][t].second = *it;
82           q.push(make_pair(n, t));
83         }
84       }
85     }
86     cout << "The problem cannot be solved." << endl;
87 NEXT:
88     cout << endl;
89   }
90   return 0;
91 }
poj/1137.cc