Posted on 2008-05-25 11:05
superman 閱讀(461)
評論(0) 編輯 收藏 引用 所屬分類:
POJ
1 /* Accepted 708K 907MS G++ 1904B */
2 #include <stack>
3 #include <queue>
4 #include <iostream>
5
6 using namespace std;
7
8 struct
9 {
10 unsigned short LastState;
11 char op;
12 }state[65536];
13
14 int main()
15 {
16 unsigned short InitState = 0;
17 for(int i = 0; i < 16; )
18 switch(getchar())
19 {
20 case '+' : InitState |= (1 << i); i++; continue;
21 case '-' : i++; continue;
22 }
23
24 for(int i = 0; i < 65536; i++)
25 state[i].op = -1;
26 state[InitState].op = -2;
27
28 queue <unsigned short> q;
29 q.push(InitState);
30
31 while(q.empty() == false)
32 {
33 unsigned short CurState = q.front(); q.pop();
34
35 if(state[0].op != -1)
36 break;
37
38 for(int i = 0; i < 16; i++)
39 {
40 unsigned short tmp = CurState;
41 tmp = tmp ^ (1 << i);
42
43 int p;
44
45 p = i - 4;
46 while(p >= 0) { tmp = tmp ^ (1 << p); p -= 4; }
47
48 p = i + 4;
49 while(p < 16) { tmp = tmp ^ (1 << p); p += 4; }
50
51 p = i / 4 * 4;
52 while(p < i) { tmp = tmp ^ (1 << p); p++; }
53
54 p = (i / 4 + 1) * 4 - 1;
55 while(p > i) { tmp = tmp ^ (1 << p); p--; }
56
57 if(state[tmp].op == -1)
58 {
59 state[tmp].LastState = CurState;
60 state[tmp].op = i;
61 q.push(tmp);
62 }
63 }
64 }
65
66 int p = 0;
67 stack <int> path;
68 while(state[p].op != -2)
69 {
70 path.push(state[p].op);
71 p = state[p].LastState;
72 }
73
74 cout << path.size() << endl;
75 while(path.empty() == false)
76 {
77 int x = path.top() / 4 + 1;
78 int y = path.top() % 4 + 1;
79 cout << x << ' ' << y << endl;
80 path.pop();
81 }
82
83 return 0;
84 }
85