题目链接：POJ-3279.Fliptile 明白题意只想看看代码的同学建议直接跳到这里：正常代码
题目
题意
给你一个0、1组成的表，翻转一个方块，可以把它本身和上下左右5个方块都从0变1、从1变0
要求你输出一个操作表，怎么反转能全0
注：
- 输出的是你操作每个方块的步数，而不是原表的翻转结果
- 如果有多个结果，输出字典序最小的那个
解题思路
- 本体需要 暴力枚举 ，把每一种翻转情况都尝试一下
但不能每个格子都独立尝试，因为最多有2^225种可能性，显然是不合理的。
但是可以只暴力第一行的翻转情况，最多只有2^15种可能性，还是能遍历的 - 第二行和之后的每一行都可以通过 上一行 的
0/1 值来确定是否要翻转 - 每一个位置的
0/1 值可以通过【本身，左边，右边，上边】四个位置的翻转情况来判断自身的最终结果 由于这一格的结果要用来判断下方的格子 是否需要翻转 因此不需要判断下方情况【下面结合代码详细说 - 对了，说是 0/1 是因为每个格子最多翻转 1 次，因为多翻是没有意义的
代码分块解析
这个模块的添加是因为，大佬在vj下面的评论区直接贴了个代码，完全没有注释，我好不容易才一点一点扒明白，所以不想浪费。
主函数
#include <iostream>
using namespace std;
typedef int hip;
#include <bitset>
int main() {
ios::sync_with_stdio(0); cin.tie(0);
// 输入m行n列数据
cin >> mLine >> nCloum;
for (hip i=1;i<=mLine;i++) for (hip j=1;j<=nCloum;j++) cin >> grass[i][j];
// 定义最小的反转次数 和 翻转情况的编号
hip ansFlip = 400;
hip ansType = -1;
// 只枚举第一行的情况，然后根据将第一行的翻转结果推算出下面每一行的翻转方式
// 第一行的情况有 2^n 种
// 如样例：
// 4 4
// 1 0 0 1
// 0 1 1 0
// 0 1 1 0
// 1 0 0 1
// iniType 的值就是 0 - 15
// 对应的第一行的结果就是
// 0000、0001、0010、0011、0100、0101、0110、0111
// 1000、1001、1010、1011、1100、1101、1110、1111
// 这16种情况
for (hip iniType = 0; iniType < 1<<nCloum; iniType++) {
// 使用bitset来自动转换成二进制
bitset<maxn> b = iniType;
// 记录这一种【第一行翻转情况】对应的所有翻转次数
hip flipNum = 0;
// 标记第一行
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++) {
f[iniType][1][cloumNo] = b[nCloum - cloumNo];
// 如果翻转增加记录数量
if (b[nCloum - cloumNo]) flipNum += 1;
}
// 标记第二行及之后的翻转情况
// 标记方式是：判断上一行对应位置是否为1，如果是，就翻转这一格
// 遍历第二行及之后的每一行
for (hip lineNo = 2; lineNo <= mLine; lineNo++)
// 遍历每一列
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++)
// after_flip() 是通过判断一个格子【本身，左边，右边，上边】四个位置是否需要翻转
// 进而返回自己在翻转过后的 0/1 值
// 此处判断的是这一列的上一行的格子，如果是1的话，就把这个格子标记为【需要翻转】
// 并且把翻转次数 +1
if (after_flip(iniType, lineNo-1, cloumNo))
f[iniType][lineNo][cloumNo] = true, flipNum += 1;
else f[iniType][lineNo][cloumNo] = false;
// 整个地图都做完标记之后，除了最后一行，上面的格子应该都是 0 了
// 如果此种翻转方案可行，那么最后一行应该也全都是 0
// end_line_all_zero() 函数会返回这种方案的最后一行是否全为 0
// 如果全为 0 而且翻转次数最少，那么就更新标记
if (end_line_all_zero(iniType) && ansFlip > flipNum)
ansType = iniType, ansFlip = flipNum;
}
// 如果方案标记还是 -1 说明没有可行方案，输出impossible
// 反之输出对应的方案【注意格式
if (ansType!=-1) {
for (hip i=1;i<=mLine;i++) {
for (hip j=1;j<=nCloum;j++) {
cout << f[ansType][i][j];
if (j == nCloum) cout << endl;
else cout << ' ';
}
}
}
else cout << "IMPOSSIBLE" << endl;
return 0;
}
after_flip() 函数 - 返回上一行的翻转结果
hip mLine, nCloum;
// 储存草地源数据的数组
bool grass[maxn][maxn];
// 储存翻转草地的表：
// 大佬的代码是，获得可行的数据编号之后重新推算一遍翻转表
// 但对于这道题并不会超限so
// 所以这里简单的把每个情况的翻转表都保存起来
bool f[1<<maxn][maxn][maxn];
//判断这里的格子有没有越界，如果没有返回 true
bool not_out_of_range(hip line, hip cloum) {
return (line > 0 && line <= mLine && cloum > 0 && cloum <= nCloum);
}
// 下一个要判断的格子变更的坐标
hip nextChange[4][2] = { {0,0}, {0,1}, {0,-1}, {-1,0} };
// 返回这个格子受到 【本身，左边，右边，上边】 翻转影响翻转完之后的结果
// 参数是 iniType 第几个数据 line 行号 cloum 列号
bool after_flip(hip iniType, hip line, hip cloum) {
// 把 tState 初始化成草地原本的状态
bool tState = grass[line][cloum];
// 遍历除了下方其他四个会影响这个格子的格子，如果没越界且有翻转就翻转一下当前草地
for (hip i = 0; i < 4; i++) {
hip nextLine = line + nextChange[i][0];
hip nextCloum = cloum + nextChange[i][1];
if (not_out_of_range(nextLine, nextCloum) && f[iniType][nextLine][nextCloum])
tState = !tState;
}
// 返回翻转后的state
return tState;
}
end_line_all_zero() 函数 - 返回最后一行是否全0
bool end_line_all_zero(hip type) {
// 此函数如题所示，但还是要调用一下 after_flip() 函数
// 如果翻转后是 1 ，说明不是全 0 返回false
for (hip cloumNo=1;cloumNo<=nCloum;cloumNo++) if (after_flip(type, mLine, cloumNo)) return false;
// 如果没有返回 false 说明翻完以后全 0 了，则返回 true
return true;
}
变量很长的代码
//
// _ _ ___ ____ ___ ____ _____
//| | | | / _ \ _ __ / ___/ _ \| _ \| ____|
//| |_| | | | | | '_ \ | | | | | | | | | _|
//| _ | | |_| | | | | | |__| |_| | |_| | |___
//|_| |_|___\___/|_| |_| \____\___/|____/|_____|
// |_____|
//
#include <iostream>
using namespace std;
typedef int hip;
#include <bitset>
const int maxn = 19;
hip mLine, nCloum;
bool grass[maxn][maxn];
bool f[1<<maxn][maxn][maxn];
bool not_out_of_range(hip line, hip cloum) {
return (line > 0 && line <= mLine && cloum > 0 && cloum <= nCloum);
}
hip nextChange[4][2] = { {0,0}, {0,1}, {0,-1}, {-1,0} };
bool after_flip(hip iniType, hip line, hip cloum) {
bool tState = grass[line][cloum];
for (hip i = 0; i < 4; i++) {
hip nextLine = line + nextChange[i][0];
hip nextCloum = cloum + nextChange[i][1];
if (not_out_of_range(nextLine, nextCloum) && f[iniType][nextLine][nextCloum])
tState = !tState;
}
return tState;
}
bool end_line_all_zero(hip type) {
for (hip cloumNo=1;cloumNo<=nCloum;cloumNo++) if (after_flip(type, mLine, cloumNo)) return false;
return true;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> mLine >> nCloum;
for (hip i=1;i<=mLine;i++) for (hip j=1;j<=nCloum;j++) cin >> grass[i][j];
hip ansFlip = 400;
hip ansType = -1;
for (hip iniType = 0; iniType < 1<<nCloum; iniType++) {
bitset<maxn> b = iniType;
hip flipNum = 0;
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++) {
f[iniType][1][cloumNo] = b[nCloum - cloumNo];
if (b[nCloum - cloumNo]) flipNum += 1;
}
for (hip lineNo = 2; lineNo <= mLine; lineNo++)
for (hip cloumNo = 1; cloumNo <= nCloum; cloumNo++)
if (after_flip(iniType, lineNo-1, cloumNo))
f[iniType][lineNo][cloumNo] = true, flipNum += 1;
else f[iniType][lineNo][cloumNo] = false;
if (end_line_all_zero(iniType) && ansFlip > flipNum)
ansType = iniType, ansFlip = flipNum;
}
if (ansType!=-1) {
for (hip i=1;i<=mLine;i++) {
for (hip j=1;j<=nCloum;j++) {
cout << f[ansType][i][j];
if (j == nCloum) cout << endl;
else cout << ' ';
}
}
}
else cout << "IMPOSSIBLE" << endl;
return 0;
}
正常代码
#include <iostream>
using namespace std;
typedef int hip;
#include <bitset>
const int maxn = 19;
hip m, n;
bool G[maxn][maxn];
bool f[1<<maxn][maxn][maxn];
bool R(hip l, hip c) {return (l > 0 && l <= m && c > 0 && c <= n);}
hip N[4][2] = { {0,0}, {0,1}, {0,-1}, {-1,0} };
bool F(hip i, hip l, hip c) {
bool t = G[l][c];
for (hip _ = 0; _ < 4; _++) {
hip nl = l + N[_][0], nc = c + N[_][1];
if (R(nl, nc) && f[i][nl][nc]) t = !t;
}
return t;
}
bool E(hip i) {
for (hip c=1;c<=n;c++) if (F(i, m, c)) return false;
return true;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> m >> n;
for (hip i=1;i<=m;i++) for (hip j=1;j<=n;j++) cin >> G[i][j];
hip r = 400;
hip t = -1;
for (hip i = 0; i < 1<<n; i++) {
bitset<maxn> b = i;
hip fn = 0;
for (hip c = 1; c <= n; c++) {
f[i][1][c] = b[n-c];
if (b[n-c]) fn += 1;
}
for (hip l = 2; l <= m; l++) for (hip c = 1; c <= n; c++)
if (F(i, l-1, c)) f[i][l][c] = true, fn += 1;
else f[i][l][c] = false;
if (E(i) && r > fn) t = i, r = fn;
}
if (t!=-1) {
for (hip i=1;i<=m;i++) for (hip j=1;j<=n;j++)
cout << f[t][i][j] << ((j==n)?"\n":" ");
}
else cout << "IMPOSSIBLE" << endl;
return 0;
}