POJ 3185 - The Water Bowls

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

概要

20個のボウルがあり，それぞれ正しい向きか反対の向きに置かれている．

あるボウルを引っくり返すと，その左右のボウルも同時に引っくり返る (つまり同時に3つの向きが変わる)． 左端または右端の場合は同時に2つの向きが変わる．

すべてのボウルが正しい向きにするのに必要な最小の手数を答える．

制約

特になし

解法

状態数は 2^20 しかないので，単に BFS するだけ．

 1 #include <iostream>
 2 #include <queue>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8   unsigned init = 0;
 9   for (int i = 0; i < 20; i++) {
10     int x;
11     cin >> x;
12     init |= x << i;
13   }
14   static int dist[1<<20];
15   fill_n(dist, 1<<20, 10000000);
16   dist[init] = 0;
17   queue<unsigned> q;
18   q.push(init);
19   while (!q.empty() && q.front() != 0) {
20     unsigned s = q.front();
21     q.pop();
22     for (int i = 0; i < 20; i++) {
23       unsigned t;
24       if (i == 0) {
25         t = s ^ 3;
26       } else if (i == 19) {
27         t = s ^ (3 << 18);
28       } else {
29         t = s ^ (7 << (i-1));
30       }
31       if (dist[s]+1 < dist[t]) {
32         dist[t] = dist[s]+1;
33         q.push(t);
34       }
35     }
36   }
37   cout << dist[0] << endl;
38   return 0;
39 }