POJ1753 Flip Games

   Flip Game题目大意是在一个4*4的棋盘上翻转棋子，翻转了一个棋子以后，他的上下左右四个方向的棋子都得跟着变色，最后使得棋盘上所有的棋子都是白色，或者都是黑色。统计要翻转的棋子的个数。分析：

      1. 棋子只有黑白两色，因此如果翻转同一个棋子不能超过一次。因为翻转两次就等于没有翻。

       2. 相同棋子之间的翻转顺序是不会影响最终翻转的结果的。

      那么上面有16个棋子，也就是16个棋子处于两种状态，需要翻转，不需要翻转，总共有2^16次方种方案。因此采用枚举的方法就可以了。

      数据结构：我们用位表示一个格子，那么4位组成一个16进制数，表示一行。用相应的位^1表示翻转，可以提前算出16种翻转的状态。如下：

1. const int state[16] = {0xC800, 0xE400, 0x7200, 0x3100,   
2.                        0x8C80, 0x4E40, 0x2720, 0x1310,  
3.                        0x08C8, 0X04E4, 0X0272, 0X0131,  
4.                        0X008C, 0X004E, 0X0027, 0X0013};  
5. //搜索采用回溯策略
6. 1. #include <stdio.h>   
   2.   
   3. #define ONLINE   
   4.   
   5. void online()  
   6. {  
   7. #ifdef ONLINE   
   8. #else   
   9.     freopen("1753.in", "r", stdin);  
   10.     freopen("1753.out","w", stdout);  
   11. #endif   
   12. }  
   13.   
   14. int map = 0;  
   15. const int END1 = 0x0000;  
   16. const int END2 = 0xFFFF;  
   17. const int state[16] = {0xC800, 0xE400, 0x7200, 0x3100,   
   18.                                 0x8C80, 0x4E40, 0x2720, 0x1310,  
   19.                                 0x08C8, 0X04E4, 0X0272, 0X0131,  
   20.                                 0X008C, 0X004E, 0X0027, 0X0013};  
   21. int result = 17;  
   22.   
   23. void read()  
   24. {  
   25.     char c;  
   26.     for (int i=0; i < 16; i ++)  
   27.     {  
   28.         c = getchar();  
   29.         //scanf("%c", &c);   
   30.         if (c == 'b')  
   31.         {  
   32.             map = map << 1;  
   33.             map =(map^1);   
   34.         }  
   35.         else if(c=='w')  
   36.         {  
   37.             map = map<<1;  
   38.         }  
   39.         else  
   40.             i --;  
   41.     }  
   42. }  
   43.   
   44. void search( int idx, int step)  
   45. {  
   46.     if (step >= result)  
   47.     {  
   48.         return;  
   49.     }  
   50.   
   51.     if (idx >= 16)  
   52.     {  
   53.         if (map == END2 || map == END1)  
   54.         {  
   55.             if (step < result)  
   56.             {  
   57.                 result = step;  
   58.             }//end if step   
   59.         }//end if map   
   60.         return;  
   61.     }  
   62.   
   63.     search(idx+1, step);  
   64.     map = map ^ state[idx];  
   65.     search(idx+1, step+1);  
   66.     map = map^state[idx];  
   67.     return;  
   68. }  
   69.   
   70. void print()  
   71. {  
   72.     if (result >= 17)  
   73.     {  
   74.         printf("Impossible");  
   75.     }  
   76.     else  
   77.         printf("%d",result);  
   78. }  
   79.   
   80. int main()  
   81. {  
   82.     online();  
   83.     read();  
   84.     search(0, 0);  
   85.     print();  
   86.     return 0;  
   87. }  

通过此题呢，我学到了用位存储信息，以前苏哥给我讲用位做八皇后，当时觉得很巧妙，但是自己没有吸收。

今天做了这道题，进一步发现了位存储矩阵信息的优点，不仅节省空间，还节省时间。妙~

一时兴起，还根据这个小算法做了一个小程序【360vsQQ】，很久没碰MFC了、这次的代码除了算法部分、其他的基本都是copy的以前写的【残缺棋盘】程序：

//主界面

//解

//说明书

本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/04/11/2443123.html，如需转载请自行联系原作者