刚开始做这题时总是在想应该用何种的策略来进行翻装，最后还是没有想出来～～～
这题过的代码的思路是用在考虑到每个点被翻装的次数只有0次或者是1次，所以对于16个点就只有2^16中请况了。再运用位运算将状态压缩到一个32位的整型当中，使用异或运算替代普通的运算。用dfs生成排列数。
代码如下：
#include <cstdlib> #include <cstring> #include <cstdio> #include <algorithm> #define START 0 #define END 65535 using namespace std;char G[6][6];int status, cpy, how[20], path[20];void pre() {how[1] = 19, how[2] =39, how[3] = 78, how[4] = 140, how[5] = 305;how[6] = 626, how[7] = 1252, how[8] = 2248, how[9] = 4880, how[10] = 10016;how[11] = 20032, how[12] = 35968, how[13] = 12544, how[14] = 29184;how[15] = 58368, how[16] = 51200;// 对每一个点进行反转所影响的区域的位压缩存储 }bool dfs(int cur, int pos, int leavings) {if (leavings == 0) {// 当组合排列完毕cpy = status;for (int i = 0; i < pos; ++i) {cpy ^= how[path[i]];}if (cpy == START || cpy == END) {return true;}else {return false;}}else {for (int i = cur; i <= 16; ++i) {path[pos] = i;if (16-pos < leavings) { // 剩余的量比要翻装的位置要少continue;}if (dfs(i+1, pos+1, leavings-1)) {return true;}}return false;} }bool OK(int times) {if (dfs(1, 0, times)) {return true;}else {return false;} }int main() {pre();// 读入数据for (int i = 1; i <= 4; ++i) {scanf("%s", G[i]+1);for (int j = 1; j <= 4; ++j) {G[i][j] = G[i][j] == 'b' ? 0 : 1;}}for (int i = 4; i >= 1; --i) {for (int j = 4; j >= 1; --j) {status <<= 1;if (G[i][j]) {status |= 1;// 将整个图压缩到一个32位的数字中 }}}int times = 0;bool finish = false;while (!finish) {if (times > 16) {break;}if (OK(times)) {finish = true;}else {++times;}}if (finish) {printf("%d\n", times);}else {puts("Impossible");}return 0; }
