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

//因为每次翻转只影响了上一行的一个格子，所以对于已知的前i行的状态，翻转至我们想要的状态所需要的步数是固定的，
//所以只需枚举第一行的所有状态， 递推即可； 

#include<bits/stdc++.h>
#define ll long long
#define ull long long

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::ios;
using std::map;

string s;
ll n,m,i,j,ans,a,b;
string c[120],d[120];

ll get(){ //快速读入； 
    char x;int f=1;
    while ((x=getchar())>'9'||x<'0')
        if (x=='-') f=-1;
    ll sum=x-'0';
    while ((x=getchar())<='9'&&x>='0')
        sum=sum*10+x-'0';
    return sum*f;
}

void overturn(ll x,ll y){   //进行题中所描述的翻转操作； 
    int dx[6]={0,0,0,0,1,-1};
    int dy[6]={0,0,1,-1,0,0};
    for (int i=1;i<=5;i++){
        a=x+dx[i];
        b=y+dy[i];
        if (a>=0&&a<n&&b>=0&&b<m){  //判断未越界； 
            d[a][b]=((d[a][b]=='0')?'1':'0');
        }
    }
    return ;
}

ll recurrence(ll state,char target){
    ll step=0;
    for (int i=0;i<n;i++){
        d[i]=c[i];
    }
    for (int i=0;i<m;i++){
        if (state&(1<<i)){  //判断第i位是否为1，其实判断是0是1都无所谓； 
            step++;
            overturn(0,i);
        }
    }
    for (int i=1;i<n;i++){
        for (j=0;j<m;j++){
            if (d[i-1][j]!=target){ //如果i，j上一行的棋子不是我们想要的状态，就翻转； 
                step++;
                overturn(i,j);
            }
        }
    }
    for (int i=0;i<m;i++){
        if (d[n-1][i]!=target) return 1000; //如果最后一行不满足条件，返回预设的最大值； 
    }
    return step;
}

int main(){
    //std::ios::sync_with_stdio(false);
    n=get();m=get();
    for (i=0;i<n;i++){
        cin>>c[i];
    }
    ans=100*10;
    for (i=0;i<(1<<m);i++){ 
        ans=std::min(ans,recurrence(i,'0')); //考虑将棋盘翻转为全是0的状态所需要的步数； 
        ans=std::min(ans,recurrence(i,'1')); //同上； 
    }
    if (ans==1000) cout<<"Impossible";
    else cout<<ans;
    return 0;
}