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

题目链接：

https://vjudge.net/problem/POJ-1753

题目大意：

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

思路：

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e6 + ;

 const int INF =  << ;

 int T, n, m;

 bool a[][], b[][], v[][];

 int dir[][] = {,,,,-,,,-};

 int f(int x)

 {

     int tot = ;

     for(int i = ; i < ; i++)

         if(x & ( << i))tot++;

     return tot;

 }

 bool judge(int x)

 {

     memcpy(b, a, sizeof(a));

     for(int i = ; i < ; i++)

     {

         if(x & ( << i))

         {

             int cx = i / ;

             int cy = i % ;

             b[cx][cy] = !b[cx][cy];

             for(int j = ; j < ; j++)

             {

                 int xx = cx + dir[j][];

                 int yy = cy + dir[j][];

                 if(xx <  || xx >=  || yy <  || yy >= )continue;

                 b[xx][yy] = !b[xx][yy];

             }

         }

     }

     int num = ;

     for(int i = ; i < ; i++)

     {

         for(int j = ; j < ; j++)

             if(b[i][j])num = num * ;

             else num = num *  + ;

     }

     if(num ==  || num == ((<<) - ))return true;

     return false;

 }

 int main()

 {

     int ans = ;

     for(int i = ; i < ; i++)

     {

         for(int j = ; j < ; j++)

         {

             char c = getchar();

             if(c == 'b')a[i][j] = ;

         }

         getchar();

     }

     for(int i = ; i < (<<); i++)

     {

         if(judge(i))

         {

             ans = min(ans, f(i));

         }

     }

     if(ans == )printf("Impossible\n");

     else cout<<ans<<endl;

     return ;

 }