poj 1753 : Flip Game (枚举+dfs)

题意：一个4*4的矩阵，每一格要么是白色，要么是黑色。现在你可以选择任意一个格变成相反的颜色，则这个格的上，下，左，右四个格也会跟着变成相反的色（如果存在的话）。问要把矩阵的所有格子变成同一个颜色，你最少需执行几次上面的操作。

思路：枚举+dfs。一个关键点：对于每一格，只能翻0或1次（易证）。因此枚举就存在2^16 =4096个状态，最多执行16次操作，因此可行。

#include<iostream>
using namespace std;
bool map[6][6], flag = false;
int step;
int dr[5] = {-1, 0, 0, 0, 1};
int dc[5] = {0, -1, 0, 1, 0};
bool isgoal(){                           //  判断矩阵的所有格子是否为同一个颜色。for(int i = 1; i <= 4; i ++)for(int j = 1; j <= 4; j ++)if(map[i][j] != map[1][1])return false;return true;
}
void flip(int row, int col){             //  翻动点(row,col)时的map[][]的变化。for(int i = 0; i < 5; i ++){int r = row + dr[i];int c = col + dc[i];map[r][c] = !map[r][c];}
}
void dfs(int row, int col, int dep){     //  点(row,col)为现在是否要操作的点。if(dep == step){flag = isgoal();return;}if(flag || row == 5) return;flip(row, col);                      //  要对点(row,col)进行翻动。if(col < 4) dfs(row, col + 1, dep + 1);else dfs(row + 1, 1, dep + 1);flip(row, col);                      //  还原状态，不对点(row,col)进行翻动。if(col < 4) dfs(row, col + 1, dep);else dfs(row + 1, 1, dep);
}
int main(){char c;for(int i = 1; i <= 4; i ++)for(int j = 1; j <= 4; j ++){cin >> c;//scanf("%c",&c);为啥scanf就不行呢if(c == 'b') map[i][j] = true;}for(step = 0; step <= 16; step ++){   //  枚举0 ~ 16 步。dfs(1, 1, 0);if(flag) break;}if(flag) cout << step << endl;else cout << "Impossible" << endl;return 0;
}