POJ 1753 Flip Game（二进制枚举）

题目大意：

有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？

解题思路：

因为只有16个格子，且只有黑白两种状态，想到用一个二进制整数来表示棋盘的状态。首先你需要明白这个题目的两个性质——任何一个格子翻偶数次等同于不翻；翻格子的顺序对最终的结果是没有影响的，也就是你如果先翻一号格子，再翻二号格子和先翻二号格子再翻一号格子是一样的效果。枚举每一种情况，总的枚举次数也不过是2^16=65536次，所以在时间复杂度上是不会产生问题的。然后在存储这个字符数组的时候利用一个value值来存储，对value进行位运算操作，枚举每一种翻与不翻的情况，记录每一次使得value == 0||value == 65535的值，得出最后步数最小的结果

AC代码：

 #include <iostream>

 #define MAX 999999

 using namespace std;

 char s[][];

 int cs[] = {,,,,,,,,,,,,,,,};

 int po[] = {,,,,,,,,,,,,,,,};

 int main()

 {

     int i,j,value = ;

     int minm = MAX;

     char c;

     for(i = ; i < ; i++)

     {

         cin >> c;

         if(c == 'b')

             value += (int)po[i];

         else

             continue;

     }

     for(i = ; i < ; i++)

     {

         int cou = ;

         int copyvalue = value;

         for(j = ; j < ; j++)

             if(i & (int)po[j])

             {

                 cou++;

                 copyvalue ^= cs[j];

             }

         if(copyvalue ==  || copyvalue == )

             if(cou <minm)

                 minm = cou;

     }

     if(minm == MAX) cout << "Impossible";

     else cout << minm << endl;

     return ;

 }

好久没写博客了，以后每天至少做一道题写一篇解题报告。已经决定要考研了，目标是浙大，加油！~！

秒客网

POJ 1753 Flip Game（二进制枚举）

相关文章