Posted on 2008-05-20 14:20
superman 阅读(230)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 2050 C++ 00:00.02 920K */
2 #include <queue>
3 #include <stdio.h>
4 #include <iostream>
5
6 using namespace std;
7
8 struct rec { int n, m; };
9
10 int main()
11 {
12 int N;
13 cin >> N;
14 while(N--)
15 {
16 int n = 0; char c;
17 for(int i = 0; i < 16; i++)
18 {
19 cin.get(c);
20 if(c == '\n')
21 {
22 i--;
23 continue;
24 }
25 if(c == 'b')
26 n |= (1 << i);
27 }
28
29 rec cur = {n, 0};
30 queue <rec> q;
31 q.push(cur);
32
33 bool repeat[65536] = {false}, find = false;
34 while(q.empty() == false)
35 {
36 cur = q.front(); q.pop();
37
38 if(cur.n == 0 || cur.n == 65535)
39 {
40 cout << cur.m << endl;
41 find = true;
42 break;
43 }
44
45 for(int i = 0; i < 16; i++)
46 {
47 int t = cur.n;
48
49 t ^= (1 << i);
50 if(i - 4 >= 0)
51 t ^= (1 << (i - 4));
52 if(i + 4 < 16)
53 t ^= (1 << (i + 4));
54 if(i % 4 - 1 >= 0)
55 t ^= (1 << (i - 1));
56 if(i % 4 + 1 < 4)
57 t ^= (1 << (i + 1));
58
59 if(repeat[t] == false)
60 {
61 repeat[t] = true;
62 rec tmp = {t, cur.m + 1};
63 q.push(tmp);
64 }
65 }
66 }
67
68 if(find == false)
69 cout << "Impossible" << endl;
70 if(N)
71 cout << endl;
72 }
73
74 return 0;
75 }
76