有一个4*4的棋盘，上面放满16个棋子，棋子一面白色，一面黑色。

玩法：

可以翻转棋盘上任意一个棋子，这样它就由白色变为黑色，或者由黑色变为白色。同时，这个棋子的上下左右紧邻的棋子也发生翻转。如果棋子的某个紧邻方向无棋子则不影响。

如下图：翻转十字箭头处的黑色棋子，则它上面的白色棋子变为黑色。右侧和下侧的黑色棋子变为白色。其左侧无棋子，则无操作。

目标是：输入一个棋盘样子，然后找出使所有棋子都为同一种颜色（黑色或者白色）的翻转次数。

分析：

1、4*4的格子共16个方格

2、每个格子有两种状态，所以棋盘共有2^16=65536种状态

3、在一个格子上翻转偶数次，相当于没有翻转

4、在一个格子上翻转奇数次，相当于之翻转了一次

5、由于格子只有两种状态，所以翻转的结果与翻转的先后顺序无关，也就是说一个解法是在选定的几个格子翻转的集合，与顺序无关

6、翻转的次数不会超过16，如果再多了，就相当于没有翻转

7、所以翻转的结果就是0至16，或者是不可能。

8、由一个初始状态（两种，全白或者全黑）经过a1-a2-a3-...-an的翻转得到的结果，再用这个组合就可以恢复原状。

9、可以用数组Types记录i情况是通过最少Types次翻转得到的。

10、模拟翻转，记录不同状态的实现次数，做成字典，把输入状态拿过来进行查找就行了

11、所有的反转的组合状况也只有2^16=65536种可能，所以用循环遍历。这样就知道所有可能的反转结果。

12、对应每一种结果i，有一个最少的反转次数Types。

13、反转用逻辑运算模拟。用整数的低16位代表16个棋盘格子的位置，如果取0，就是黑的，如果取1，就是白的。

14、反转x格子里的棋子，会带动反转相应的棋子。比如反转0号棋子，1号和4号也会反转。那么，将棋盘状态数stat与（10011）b=19，这个数字做异化运算就可以得到所有棋子反转的结果。这些做异或的数字放在数组mask[]中。

0   1   2   3

4   5   6   7

8   9  10  11

12 13 14 15

代码：

1. public class FlipThink {
   
2.         public static int[] mask = new int[]{19,39,78,140,
   
3.                                                         305,626,1252,2248,
   
4.                                                         4880,10016,20032,35968,
   
5.                                                         12544,29184,58368,51200};
   
6.         public static int flips(int stats,int i) {
   
7.                 return (stats ^ mask[i]);
   
8.         }
   
9.         public static void main(String[] args) {
   
10.                 //
    
11.                 int[] Types = new int[65536];
    
12.                 for(int i=0;i<65536;i++) {
    
13.                         Types[i] = 99999999;
    
14.                 }
    
15.                 for(int stat = 0 ; stat < 65536; stat++) {
    
16.                         //遍历所有反转组合情况
    
17.                         int result = 0;//以0---black 即全是黑色开始，为一个情况。1等会儿再说
    
18.                         int times = 0;//这个情况一共反转了几个棋子
    
19.                         for(int i = 0; i < 16; i++) {//遍历所有二进制位
    
20.                                 if(((stat>>>i) & 1) == 1) {//检查哪一个二进制位为1，就反转那个棋子
    
21.                                         times++;
    
22.                                         result = flips(result,i);
    
23.                                 }
    
24.                         }
    
25.                         if(Types[result] > times) Types[result] = times;
    
26.                 }
    
27.                 for(int stat = 0 ; stat < 65536; stat++) {
    
28.                         //遍历所有反转组合情况
    
29.                         int result = 1;//以1---白，即全为白色开始，为一个情况
    
30.                         int times = 0;//这个情况一共反转了几个棋子
    
31.                         for(int i = 0; i < 16; i++) {//遍历所有二进制位
    
32.                                 if(((stat>>>i) & 1) == 1) {//检查哪一个二进制位为1，就反转那个棋子
    
33.                                         times++;
    
34.                                         result = flips(result,i);
    
35.                                 }
    
36.                         }
    
37.                         if(Types[result] > times) Types[result] = times;
    
38.                 }
    
39.                 int[] a = new int[16];
    
40.                 for(int i=0;i<16;i++) {
    
41.                         a[i] = 0;
    
42.                 }
    
43.                 //1---white   0-----black
    
44.                 /*
    
45.                         a[0]        a[1]        a[2]        a[3]
    
46.                         a[4]        a[5]        a[6]        a[7]
    
47.                         a[8]        a[9]        a[10]        a[11]
    
48.                         a[12]        a[13]        a[14]        a[15]
    
49.                 */
    
50.                 a[1]=a[2]=a[6]=a[9]=a[10]=a[13]=a[14]=a[15]=1;
    
51.                 int sum = 0;
    
52.                 for(int i=0;i<16;i++) {
    
53.                         if(a[i] == 1) {
    
54.                                 sum += 1<<i;
    
55.                         }
    
56.                 }
    
57.                 System.out.println(Types[sum]);
    
58.                 /*
    
59.                 for(int i=0;i<65536;i++) {
    
60.                         if(Types[i] !=99999999)
    
61.                                 System.out.println("i="+i+":"+Types[i]);
    
62.                 }
    
63.                 */
    
64.         }
    
65. }

复制代码

挺有意思的