Flip Game

OJ
POJ
题目描述
![](http://ww3.sinaimg.cn/large/9bcfe727jw1fa3jk4clc9g208w07wmx0.gif)

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

解题思想
Queue

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

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

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

DFS

4x4得棋盘最多需要翻转16次就可以完成，因为同一位置上得两次翻转等于没有翻转。
可以根据步数从0到16依次枚举，第一个符合条件的就是最小的步数，为了容易深搜，可以设定顺序为一行一行深搜，当一行搜完时从下一行开头搜。下面的代码也可以使用bit的思想压缩空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int DFS(int i, int j, int dp) {
    // step表示当前尝试的步数上限
    // dp表示在step步数上限的前提下，当前的步数
    if(dp == step){
        flag=range();
        return 0;
    }
    if(flag||i==4) return 1;
    turn(i,j); //翻转当前位置
    if(j<3)
        DFS(i,j+1,dp+1); // 下一个列
    else
        DFS(i+1,0,dp+1); // 下一行
    turn(i,j); // 消除当前位置的翻转
    if(j<3)
        DFS(i,j+1,dp); // 当前位置不动的情况下，到下一列
    else
        DFS(i+1,0,dp); // 当前位置不动的情况下，到下一行
    return 0;
}
/*
    其余代码省略
*/
int main() {
    // step表示步数0到16枚举
    for(step=0; step<=16; step++) {
        flag=0;
        // 从(0,0)开始，开始第0步
        dfs(0,0,0);
        // 如果找到了，输出即可。因为步数上限step是逐渐提高的
        if(flag)break;
    }
}

分享到