刚开始做这题时总是在想应该用何种的策略来进行翻装，最后还是没有想出来～～～
这题过的代码的思路是用在考虑到每个点被翻装的次数只有0次或者是1次，所以对于16个点就只有2^16中请况了。再运用位运算将状态压缩到一个32位的整型当中，使用异或运算替代普通的运算。用dfs生成排列数。
代码如下：
#include#include #include #include #define START 0#define END 65535using 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;}