POJ-1753 Flip Game---二进制枚举子集

题目链接：

题目大意：

有4*4的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑->白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几个格子可以使4*4的正方形变为纯白或者纯黑？

思路：

直接二进制枚举16个元素的子集，判断哪些点需要进行翻转操作

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<queue>
 7 #include<stack>
 8 #include<map>
 9 using namespace std;
10 typedef long long ll;
11 const int maxn = 1e6 + 10;
12 const int INF = 1 << 30;
13 int T, n, m;
14 bool a[6][6], b[6][6], v[6][6];
15 int dir[4][2] = {1,0,0,1,-1,0,0,-1};
16 int f(int x)
17 {
18     int tot = 0;
19     for(int i = 0; i < 16; i++)
20         if(x & (1 << i))tot++;
21     return tot;
22 }
23 bool judge(int x)
24 {
25     memcpy(b, a, sizeof(a));
26     for(int i = 0; i < 16; i++)
27     {
28         if(x & (1 << i))
29         {
30             int cx = i / 4;
31             int cy = i % 4;
32             b[cx][cy] = !b[cx][cy];
33             for(int j = 0; j < 4; j++)
34             {
35                 int xx = cx + dir[j][0];
36                 int yy = cy + dir[j][1];
37                 if(xx < 0 || xx >= 4 || yy < 0 || yy >= 4)continue;
38                 b[xx][yy] = !b[xx][yy];
39             }
40         }
41     }
42     int num = 0;
43     for(int i = 0; i < 4; i++)
44     {
45         for(int j = 0; j < 4; j++)
46             if(b[i][j])num = num * 2;
47             else num = num * 2 + 1;
48     }
49     if(num == 0 || num == ((1<<16) - 1))return true;
50     return false;
51 }
52 int main()
53 {
54     int ans = 10000;
55     for(int i = 0; i < 4; i++)
56     {
57         for(int j = 0; j < 4; j++)
58         {
59             char c = getchar();
60             if(c == 'b')a[i][j] = 1;
61         }
62         getchar();
63     }
64     for(int i = 0; i < (1<<16); i++)
65     {
66         if(judge(i))
67         {
68             ans = min(ans, f(i));
69         }
70     }
71     if(ans == 10000)printf("Impossible
");
72     else cout<<ans<<endl;
73     return 0;
74 }