当前位置 : 首页 » 博文聚焦 » 正文

POJ1753 Flip Games

分类 : 博文聚焦 | 发布时间 : 2012-04-11 22:53:00 | 浏览 : 0

开始的时候自己读完题目,知道它的目的,但是如何做,脑子里还没有一个清晰的思路。因为某种原因,我直接网上搜了别人的思路,知道了题目的思路,下午边上课边写程序,发现原来是这么简单的题目。下面是给我启发的那篇文章:

转载自:http://blog.csdn.net/zengniao/article/details/6644793  

题目:http://poj.org/problem?id=1753

   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. //搜索采用回溯策略
    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的以前写的【残缺棋盘】程序:

//主界面

//解

//说明书

相关阅读: