Posted on 2008-04-16 02:34
superman 閱讀(338)
評論(0) 編輯 收藏 引用 所屬分類:
URAL
1 /* C++ Accepted 0.015 380 KB */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct rec { int n, m; };
8
9 int main()
10 {
11 int n = 0; char c;
12 for(int i = 0; i < 16; i++)
13 {
14 cin.get(c);
15 if(c == '\n')
16 {
17 i--;
18 continue;
19 }
20 if(c == 'b')
21 n |= (1 << i);
22 }
23
24 rec cur = {n, 0};
25 queue <rec> q;
26 q.push(cur);
27
28 bool repeat[65536] = {false}, find = false;
29 while(q.empty() == false)
30 {
31 cur = q.front(); q.pop();
32
33 if(cur.n == 0 || cur.n == 65535)
34 {
35 cout << cur.m << endl;
36 find = true;
37 break;
38 }
39
40 for(int i = 0; i < 16; i++)
41 {
42 int t = cur.n;
43
44 t ^= (1 << i);
45 if(i - 4 >= 0)
46 t ^= (1 << (i - 4));
47 if(i + 4 < 16)
48 t ^= (1 << (i + 4));
49 if(i % 4 - 1 >= 0)
50 t ^= (1 << (i - 1));
51 if(i % 4 + 1 < 4)
52 t ^= (1 << (i + 1));
53
54 if(repeat[t] == false)
55 {
56 repeat[t] = true;
57 rec tmp = {t, cur.m + 1};
58 q.push(tmp);
59 }
60 }
61 }
62
63 if(find == false)
64 cout << "Impossible" << endl;
65
66 return 0;
67 }
68