POJ_1753

    时隔多日，已经是第3次写这个题目了，在熟悉了位运算之后使得更有效率地解决了这个问题。

    同时，这个题目在枚举上也有一点小的技巧。如果要是暴力枚举的话，一旦棋盘到了16*16的话显然就吃不消了（一个东欧区域赛的题目），实际上我们完全可以只枚举第一行的操作，之后，如果我们想把棋子全部翻成一种颜色的话，那么第二行的操作就是固定的了（因为第一行的棋子的状态对第二行棋子的翻转进行了约束，如果想把第一行的棋子变成白色，那么第二行中位于第一行黑色棋子下方的位置必须翻转，反之亦然），那么第三行、第四行的操作显然也是固定的了。

    这样即使是16*16的棋盘也只有15*16*2^16的复杂度，是可以接受的。

#include
     
       #include
      
        int fresh, steps, dx[] = {
   0, -1, 1, 0, 0}, dy[] = {
   0, 0, 0, -1, 1}; void init() {
   char ch;     fresh = 0; for(int i = 0; i < 4; i ++)     {
   for(int j = 0; j < 4; j ++)             fresh = (fresh << 1) + ((ch = getchar()) == 'b' ? 1 : 0);         getchar();     } } void flip(int x, int y, int &st) {
   if(x >= 0 && x < 4 && y >= 0 && y < 4)         st ^= 1 << (x * 4 + y); } void dfs(int cur, int num, int st, int flag) {
   if(cur == 4)     {
   if(st == 0xffff || st == 0)             steps = num < steps ? num : steps; return;     } int x, y; for(int i = cur - 1, j = 0; j < 4; ++ j) if(((st & (1 << (i * 4 + j))) >> (i * 4 + j)) ^ flag )         {
   for(int k = 0; k < 5; ++ k)             {
                   x = cur + dx[k];                 y = j + dy[k];                 flip(x, y, st);             }             ++ num;         }     dfs(cur + 1, num, st, flag); } int solve() {
       steps = 0x7fffffff; for(int i = 0; i < 16; ++ i)     {
   int num = 0, st = fresh, x, y; for(int j = 0; j < 4; ++ j)         {
   if(i & (1 << j))             {
   for(int k = 0; k < 5; k ++)                 {
                       x = 0 + dx[k];                     y = j + dy[k];                     flip(x, y, st);                 }                 num ++;             }         }         dfs(1, num, st, 0);         dfs(1, num, st, 1);     } return steps == 0x7fffffff ? -1 : steps; } int main() {
       init(); if(solve() != -1)         printf("%d\n", steps); else         printf("Impossible\n"); return 0; }