题解 | #牛可乐的翻转游戏#

//采用了大佬的题解，由于移动某一枚棋子上下左右中，上只有一个，所以将当前行作为上一定能移动到想要的效果。
//但是这样的话虽然合理，但是对于第一行没有进行任何的移动，这样会失去一些情况导致失败。所以将第一行上面再加一行
//从而让第一行有枚举移动的可能性，所以对于新加的第一行需要通过状态压缩DP使用01位运算枚举所有的可能性
//然后在最后统一的是0还是1这两个当中同样进行两次枚举。每次枚举的结果挑选最小值即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <limits.h>
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAXN = 101;
const int MAXM = 11;
ll a[MAXN][MAXM], A[MAXN][MAXM];
int n, m;
//进行上下左右以及自身的翻转
void reverses(int x, int y) {
    int i=0;
    //提供移动的数组
    int y1[6] = {0, 0,0, -1, 1};
    int x1[6] = {0, 1, 2,1, 1};
    for (i;i<6;i++) {
        if (x+x1[i]>=0&&x+x1[i]<n&&y+y1[i]>=0&&y+y1[i]<m) {
            a[x+x1[i]][y+y1[i]] = a[x+x1[i]][y+y1[i]]==0? 1:0;
        }
    }
}
ll get_num(int i, int target) {
    ll step = 0;
    for (int j=0;j<n;j++) {
        for (int k=0;k<m;k++) {
            a[j][k] = A[j][k];
        }
    }
    //对新加的第一行进行统一，也就是将原先第一行进行一个调整
    for (int j=0;j<m;j++) {
        if (i&(1<<j)) {
            step++;
            reverses(-1, j);
        }
    }
    //
    for (int j=0;j<n-1;j++) {
        for (int k=0;k<m;k++) {
            if (a[j][k]!=target) {
                step++;
                reverses(j, k);
            }
        }
    }
    for (int k=0;k<m;k++) {
        if (a[n-1][k]!=target) {
            return INT_MAX;
        }
    }
    return step;
}

int main() {
//     IOS;
    ll ans = INT_MAX-1;
    cin>>n>>m;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            scanf("%1d", &A[i][j]);
        }
    }
    for (int i=0;i<(1<<m);i++) {
        ans = min(ans, get_num(i, 1));//全部变成1的情况
        ans = min(ans, get_num(i, 0));//全部变成0的情况
    }
    if (ans == INT_MAX-1) {
        cout<<"Impossible";
        return 0;
    }
    cout<<ans;
    
    return 0;
}