首页 > 代码库 > poj1753 Flip Game
poj1753 Flip Game
题意：4*4的正方形，每个格子有黑白两面，翻转格子使得4*4个格子显示全黑或全白，翻转要求：选中的那个格子，以及其上下左右相邻的格子（如果存在）要同时翻转。输出最小的达到要求的翻转次数或者Impossible（如果不可能）
题目链接：http://poj.org/problem?id=1753
分析：因为每个格子只有黑白两面，所以对于每个格子来说，要么不翻转，要么翻转一次，因为翻转奇数次结果和翻转一次得到的效果是一样的，而翻转偶数次得到的效果和不翻转是一样的，则总共有16个格子，最多要翻转16次，每个格子有黑白两种颜色，假设每一次面临的4*4正方形代表一个状态，则总共有2^16种状态，可以用16位二进制数表示,每一位1代表‘b‘(白)，0代表‘w‘(黑)。当状态为（0或者65535）时则达到要求。
注意：1.因为只用求最少次数，用bfs做，将每一个没有访问到的状态 (用vis[]数组标记) 加入到队列中，如果游戏无法完成，状态必定会形成循环，由于重复状态不会再次入队，所以最后的队列一定会是空队列。当队列为空时说明此时还未达到要求，则是Impossible
2.二进制运算，翻转某一个格子即指将1变成0，0变成1.这里可以用异或运算的性质，1^0=1,0^0=0;所以只用将需要翻转的那个格子对应的16位二进制数的位置为1，其他不翻转的格子对应的16位二进制数的位置为0得到一个数和当前状态的16位二进制数异或即可得到翻转后的状态。
例如：
bwwbbbwbbwwbbwww
的状态可以表示为1001 1101 1001 1000 (二进制)，如果我现在要翻转第一行第一个格子，则可以用此二进制数和1100 1000 0000 0000 异或，则可以得到下一个状态next=1001 1101 1001 1000 ^ 1100 1000 0000 0000 = 0101 0101 1001 1000
即：
wbwbwbwbbwwbbwww
可以得到转换每一个格子需要异或的二进制数(十进制表示)：
int change[16] = {
51200,58368,29184,12544,
35968,20032,10016,4880,
2248,1252,626,305,
140,78,39,19
};
代码：
1 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 2 void init() 3 { 4 int i,j,x,y,t,temp; 5 for(i=0;i<4;++i) 6 { 7 for(j=0;j<4;++j) 8 { 9 temp = 0; 10 temp ^= (1<<(15 - ( i*4 + j ))); 11 for(t=0;t<4;++t) 12 { 13 x = i + dir[t][0]; 14 y = j + dir[t][1]; 15 if(x<0 || y<0 || x>3 || y>3) 16 continue; 17 temp ^= (1<<((3-x)*4+3-y)); 18 } 19 cout<<temp<<" "; 20 } 21 cout<<endl; 22 } 23 }
完整代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cmath> 5 #include<string> 6 #include<cstring> 7 #include<algorithm> 8 #include<vector> 9 using namespace std;10 char m[4][4];11 //int di[4][2]={{1,0},{0,1},{-1,0},{0,-1}};12 struct Node13 {14 int state,step;15 }nod[100000];16 int vis[100000];17 /*18 int change[16] = //16种状态转换，对应4*4的翻子位置 方法2.直接异或得到状态19 {20 51200,58368,29184,12544,21 35968,20032,10016,4880,22 2248,1252,626,305,23 140,78,39,1924 };25 */26 int getChang(int stat,int x,int y) //方法1.翻转需要翻转的格子27 {28 int tp=stat;29 tp^=(1<<(15-x*4-y));30 if(x>0) tp^=(1<<(15-(x-1)*4-y)); //上31 if(x<3) tp^=(1<<(15-(x+1)*4-y)); //下32 if(y>0) tp^=(1<<(15-x*4-y+1)); //左33 if(y<3) tp^=(1<<(15-x*4-y-1)); //右34 return tp;35 }36 int bfs(Node cur)37 {38 queue<Node>q;39 q.push(cur);40 Node next;41 vis[cur.state]=1;42 43 while(!q.empty())44 {45 cur=q.front();46 q.pop();47 if(cur.state==0||cur.state==65535) //判断是否全黑/全白48 return cur.step;49 for(int i=0;i<4;i++)50 {51 for(int j=0;j<4;j++)52 {53 next.state=getChang(cur.state,i,j); //按部得到状态54 //next.state=cur.state^change[i]; //直接异或得到状态 (循环要改为for(int i=0;i<16;i++) )55 next.step=cur.step+1;56 if(next.state==0||next.state==65535)57 return next.step;58 if(vis[next.state]) //是否已经入队过59 continue;60 q.push(next);61 vis[next.state]=1;62 }63 }64 }65 return -1;66 }67 int main()68 {69 memset(vis,0,sizeof(vis));70 int tmp=0;71 for(int i=0;i<4;i++)72 {73 cin>>m[i];74 for(int j=0;j<4;j++)75 {76 if(m[i][j]==‘b‘)77 tmp+=(1<<(15-4*i-j));78 }79 }80 Node cur;81 cur.state=tmp;82 cur.step=0;83 int ans=bfs(cur);84 if(ans==-1)85 printf("Impossible\n");86 else87 printf("%d\n",ans);88 return 0;89 }
poj1753 Flip Game