POJ 1753 Flip Game (黑白棋) （状态压缩+BFS）

题目大意：有一个4*4的方格，每个方格中放一粒棋子，这个棋子一面是白色，一面是黑色。游戏规则为每次任选16颗中的一颗，把选中的这颗以及它四周的棋子一并反过来，当所有的棋子都是同一个颜色朝上时，游戏就完成了。现在给定一个初始状态，要求输出能够完成游戏所需翻转的最小次数，如果初始状态已经达到要求输出0。如果不可能完成游戏，输出Impossible。

主要思想：

1.如果用一个4*4的数组存储每一种状态，不但存储空间很大，而且在穷举状态时也不方便记录。因为每一颗棋子都只有两种状态，所以可以用二进制0和1表示每一个棋子的状态，则棋盘的状态就可以用一个16位的整数唯一标识。而翻转的操作也可以通过通过位操作来完成。显然当棋盘状态id为0(全白)或65535(全黑)时，游戏结束。

2.对于棋盘的每一个状态，都有十六种操作，首先要判断这十六种操作之后是否有完成的情况，如果没有，则再对这十六种操作的结果分别再进行上述操作，显然这里就要用到队列来存储了。而且在翻转的过程中有可能会回到之前的某种状态，而这种重复的状态是不应该再次入队的，所以维护isVis[i]数组来判断id==i的状态之前是否已经出现过，如果不是才将其入队。如果游戏无法完成，状态必定会形成循环，由于重复状态不会再次入队，所以最后的队列一定会是空队列。

3.由于0^1=1，1^1=0，所以翻转的操作可以通过异或操作来完成，而翻转的位置可以通过移位来确定。

 # include <iostream>
 # define N 65536
 using namespace std;
 
 int q[N*2];
 int front, rear, i, j, id = 0, tmp;
 bool vis[N];                 //标记状态是否出现过
 int step[N];                 //记录到达id==i时状态翻转所需次数
 char color;                     
 
 int main(void)
 {
     for(i = 0; i < 4; i++)
         for(j = 0; j < 4; j++)
         {
             cin >> color;                //输入初始状态并转换为id
             id <<= 1;
             if(color == 'b')
                 id++;
         }
     if(id == 0 || id == 65535)
     {
         cout << 0 << endl;                //如果初始状态满足直接输出
         return 0;
     }
     q[rear++] = id;                     //初始状态id入队
     vis[id] = true;
     step[id] = 0;                       //到达初始状态所需次数置0
     while(front < rear)                 //队列不为空继续操作
     {
         id = q[front++];                //队头元素出队
         for(i = 0; i < 4; i++)
             for(j = 0; j < 4; j++)
             {
                 tmp = id;                //需要遍历队头元素的16种操作  每次还原tmp
                 if(i == 0)
                     tmp ^= 1 << (11-4*i-j);          //翻转的位置为15-(4*(i+1)+j)
                 else if(i == 3)
                     tmp ^= 1 << (19-4*i-j);          //翻转的位置为15-(4*(i-1)+j)
                 else
                 {
                     tmp ^= 1 << (11-4*i-j);
                     tmp ^= 1 << (19-4*i-j);
                 }
                 if(j == 0)
                     tmp ^= 3 << (14-4*i-j);         //翻转的位置为15-(4*i+j)、15-(4*i+j+1)
                 else if(j == 3)
                     tmp ^= 3 << (15-4*i-j);         //翻转的位置为15-(4*i+j-1)、15-(4*i+j)
                 else
                 {
                     tmp ^= 7 << (14-4*i-j);          //翻转的位置为15-(4*i+j-1)、15-(4*i+j)、15-(4*i+j+1)
                 }
                 if(tmp == 0 || tmp == 65535)
                 {
                     cout << step[id]+1 << endl;
                     return 0;
                 }
                 if(!vis[tmp])          //如果是新状态   入队 
                 {
                     q[rear++] = tmp;
                     vis[tmp] = true;
                     step[tmp] = step[id]+1;          // 当前次数=到达队头元素所需次数+1
                 }
             }
     }
     cout << "Impossible" << endl;
 
     return 0;
 }

View Code

第一次做状态压缩的题，也是现学现卖，有些像位运算的公式什么的还是理解的不是很透彻，关于状态压缩的题还是需要再多做几个。

POJ 1753 Flip Game (黑白棋) （状态压缩+BFS）

相关推荐