superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

POJ 2965 - The Pilots Brothers' refrigerator

Posted on 2008-05-25 11:05 superman 阅读(440) 评论(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理