【回炉重造】POJ-3279.Fliptile 题解_综合

【回炉重造】POJ-3279.Fliptile 题解

我好弱，记录一个想了两天也想不到的暴力

题目链接：POJ-3279.Fliptile
明白题意只想看看代码的同学建议直接跳到这里：正常代码

题目
题意
解题思路
代码分块解析
- 主函数
- after_flip() 函数 - 返回上一行的翻转结果
- end_line_all_zero() 函数 - 返回最后一行是否全0
变量很长的代码
正常代码

题目

请添加图片描述

题意

给你一个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的话，就把这个格子标记为【需要翻转】// 并且把翻转次数 +1if (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;}// 返回翻转后的statereturn tState;
}

end_line_all_zero() 函数 - 返回最后一行是否全0

bool end_line_all_zero(hip type) {
    // 此函数如题所示，但还是要调用一下 after_flip() 函数// 如果翻转后是 1 ，说明不是全 0 返回falsefor (hip cloumNo=1;cloumNo<=nCloum;cloumNo++) if (after_flip(type, mLine, cloumNo)) return false;// 如果没有返回 false 说明翻完以后全 0 了，则返回 truereturn 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;
}