首页 > 代码库 > POJ 1753 Flip Game（二进制枚举）
POJ 1753 Flip Game（二进制枚举）
题目地址链接：http://poj.org/problem?id=1753
题目大意：
有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？
解题思路：
因为只有16个格子，且只有黑白两种状态，想到用一个二进制整数来表示棋盘的状态。首先你需要明白这个题目的两个性质——任何一个格子翻偶数次等同于不翻；翻格子的顺序对最终的结果是没有影响的，也就是你如果先翻一号格子，再翻二号格子和先翻二号格子再翻一号格子是一样的效果。枚举每一种情况，总的枚举次数也不过是2^16=65536次，所以在时间复杂度上是不会产生问题的。然后在存储这个字符数组的时候利用一个value值来存储，对value进行位运算操作，枚举每一种翻与不翻的情况，记录每一次使得value =http://www.mamicode.com/= 0||value == 65535的值，得出最后步数最小的结果
AC代码：
1 #include <iostream> 2 #define MAX 999999 3 using namespace std; 4 char s[4][4]; 5 int cs[16] = {19,39,78,140,305,626,1252,2248,4880,8992,20032,35968,12544,29184,58368,51200}; 6 int po[16] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; 7 int main() 8 { 9 int i,j,value = http://www.mamicode.com/0;10 int minm = MAX;11 char c;12 for(i = 0; i < 16; i++)13 {14 cin >> c;15 if(c == ‘b‘)16 value += (int)po[i];17 else18 continue;19 }20 for(i = 0; i < 65536; i++)21 {22 int cou = 0;23 int copyvalue =http://www.mamicode.com/ value;24 for(j = 0; j < 16; j++)25 if(i & (int)po[j])26 {27 cou++;28 copyvalue ^= cs[j];29 }30 if(copyvalue =http://www.mamicode.com/= 0 || copyvalue =http://www.mamicode.com/= 65535)31 if(cou <minm)32 minm = cou;33 }34 if(minm == MAX) cout << "Impossible";35 else cout << minm << endl;36 return 0;37 }
好久没写博客了，以后每天至少做一道题写一篇解题报告。已经决定要考研了，目标是浙大，加油！~！
POJ 1753 Flip Game（二进制枚举）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。