POJ - 1753 - Flip Game = 枚举

http://poj.org/problem?id=1753

题意：4*4方阵，每次翻转周围的棋子，问全部同色的最小步数。

好像cf有个题是这样的，一般就枚举第一行，然后第一行没有翻的就只能从第二行去影响它，这样前三行都是可以单点调整的，最后一行要是不是全同色就直接false。

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

char cg[6][6];
char g[6][6];

inline void copyg() {
    memcpy(g, cg, sizeof(cg));
}

inline void flip(int i, int j) {
    g[i][j] = !g[i][j];
    g[i - 1][j] = !g[i - 1][j];
    g[i + 1][j] = !g[i + 1][j];
    g[i][j - 1] = !g[i][j - 1];
    g[i][j + 1] = !g[i][j + 1];
    /*for(int i = 1; i <= 4; ++i) {
        for(int j = 1; j <= 4; ++j) {
            printf("%d", (int)g[i][j]);
        }
        printf("\n");

    }
    printf("\n");*/
}

int main() {
#ifdef Yinku
    freopen("Yinku.in", "r", stdin);
#endif // Yinku
    for(int i = 1; i <= 4; ++i) {
        scanf("%s", cg[i] + 1);
        for(int j = 1; j <= 4; ++j) {
            cg[i][j] = (cg[i][j] == 'b') ? 0 : 1;
        }
    }
    int minans = 1e9;
    for(int k = 0; k < (1 << 4); ++k) {

        copyg();
        int cnt = 0;
        for(int j = 0; j < 4; ++j) {
            if((k >> j) & 1) {
                flip(1, j + 1);
                ++cnt;
            }
        }

        for(int i = 1; i <= 3; ++i) {
            for(int j = 1; j <= 4; ++j) {
                if(g[i][j] == 1) {
                    flip(i + 1, j);
                    ++cnt;
                }
            }
        }
        int suc = 1;
        for(int j = 1; j <= 4; ++j) {
            if(g[4][j] == 1) {
                suc = 0;
                break;
            }
        }
        if(suc) {
            minans = min(minans, cnt);
        }
        copyg();
        cnt = 0;
        for(int j = 0; j < 4; ++j) {
            if((k >> j) & 1) {
                flip(1, j + 1);
                ++cnt;
            }
        }
        for(int i = 1; i <= 3; ++i) {
            for(int j = 1; j <= 4; ++j) {
                if(g[i][j] == 0) {
                    flip(i + 1, j);
                    ++cnt;
                }
            }
        }
        suc = 1;
        for(int j = 1; j <= 4; ++j) {
            if(g[4][j] == 0) {
                suc = 0;
                break;
            }
        }
        if(suc) {
            minans = min(minans, cnt);
        }
    }
    if(minans >= 10000)
        puts("Impossible");
    else
        printf("%d\n", minans);
}

POJ - 1753 - Flip Game = 枚举

原文：https://www.cnblogs.com/Inko/p/11717078.html