poj 1753 、poj 2965 （枚举）（位运算）

位运算资料：http://baike.baidu.com/view/379209.htm（百度百科）

poj 1753 Flip Game

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<queue>
 5 using namespace std;
 6 struct node
 7 {
 8     int data;
 9     int step;
10 };
11 queue<node>que;
12 int vis[65536];
13 void bfs(int x)
14 {
15     struct node t,s;
16     t.data=x;
17     t.step=0;
18     while(!que.empty())
19         que.pop();
20     que.push(t);
21     vis[x]=1;
22     while(!que.empty())
23     {
24         t=que.front();
25         que.pop();
26         int c=t.data;
27         if(c==0||c==65535)//c=0时，全为白；c=65535时，全为黑；
28         {
29             printf("%d
",t.step);
30             return;
31         }
32         for(int i=0; i<16; i++)//枚举
33         {
34             int k=c;
35             k=k^(1<<i);//翻动第i个
36             if(i>3)
37                 k=k^(1<<(i-4));//翻动相邻
38             if(i< 12)
39                 k=k^(1<<(i+4));
40             if(i%4!=0)
41                 k=k^(1<<(i-1));
42             if(i%4!=3)
43                 k=k^(1<<(i+1));
44             s.data=k;
45             s.step=t.step+1;
46             if(!vis[k])
47             {
48                 vis[k]=1;
49                 que.push(s);
50             }
51        }
52     }
53     printf("Impossible
");
54 }
55 int main()
56 {
57     int x=0; //定义二进制数 X，其初始值为 0；（二进制数化为十进制数在0--65535之间）
58     int i,j;
59     char b[16][16];//定义字符数组
60     for(i=0; i<4; i++)//输入数组元素，用x记录其状态
61     {
62         scanf("%s",b[i]);
63         for(j=0;j<4;j++)
64         {
65             if(b[i][j]=='b')//位运算（<< 无符号右移）
66                  x=(x << 1)+1;
67             else x=x << 1;
68         }
69 
70     }
71     memset(vis,0,sizeof(vis));
72     bfs(x);
73     return 0;
74 }

View Code

poj 2965 The Pilots Brothers' refrigerator

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

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<queue>
 5 using namespace std;
 6 struct node
 7 {
 8     int data;
 9     int step;
10 };
11 queue<node>que;
12 int vis[65536];
13 node p[65536],t,q;
14 void bfs(int x)
15 {
16     while(!que.empty())
17         que.pop();
18     t.data=x;
19     t.step=0;
20     que.push(t);
21     vis[x]=1;
22     while(!que.empty())
23     {
24         t=que.front();
25         que.pop();
26         if(t.data==0)
27         {
28             printf("%d
",t.step);
29             int o=t.data;
30             for(int j=0; j<t.step; j++)
31             {
32                 printf("%d %d
",4-p[o].step/4,4-p[o].step%4);
33                 o=p[o].data;
34             }
35             return ;
36         }
37         for(int i=0; i<16; i++)
38         {
39             int c=t.data;
40             int n;
41             c=c^(1<<i);
42             int k=(i/4)*4;
43             for( n=k; n<=k+3; n++)
44                 c=c^(1<<n);
45             for(n=i%4; n<16; n+=4)
46                 c=c^(1<<n);
47             q.data=c;
48             q.step=t.step+1;
49             if(!vis[c])
50             {
51                 que.push(q);
52                 vis[c]=1;
53                 p[c].data=t.data;
54                 p[c].step=i;
55             }
56         }
57     }
58 }
59 int main()
60 {
61     int i,j;
62     char s[16];
63     int x=0;
64     for(i=0; i<4; i++)
65     {
66         scanf("%s",s);
67         for(j=0; j<4; j++)
68         {
69             if(s[j]=='+')
70                 x=(x<<1)+1;
71             else  x=x<<1;
72         }
73     }
74     memset(vis,0,sizeof(vis));
75     bfs(x);
76     return 0;
77 }

View Code