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

//https://ac.nowcoder.com/acm/problem/235250
//状态压缩枚举
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define ll long long
#define inf INT_MAX
#define js ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
typedef  pair<int,int> PII;
const int  N = 110,M=15;
int n,m;
int a[N][M],b[N][M];//因为不知道是翻到0或者1的step哪个更少，所以模拟两遍
vector<int> v;
int mx[5]={0,-1,1,0,0};//本身及上下左右翻转
int my[5]={0,0,0,-1,1};

bool jud(int x,int y) {//判断边界
    return x>=0&&x<n&&y>=0&&y<m;
}
void reverse(int x,int y){//模拟翻转的过程，以x,y为中心进行
    for (int i=0;i<5;++i) {
        int xx=x+mx[i],yy=y+my[i];
        if (jud(xx,yy)) a[xx][yy]=a[xx][yy]==0?1:0;
    }
}
ll solve(int i,int tar) {
    ll step=0;
    forn(j,n)
        forn(k,m)
    a[j][k]=b[j][k];
    for (int j=0;j<m;++j) {//先对第一行进行处理
        if (i&(1<<j)) {//这里是位与的知识，循环外的i是0-2的m次，这条语句在于判断
            step++;
            reverse(0,j);
        }
    }/*
    这里的reverse与下面循环的没有关系，
    上面是在尝试将第一行每个元素都翻一遍，
    我把他理解成二进制枚举对实际第一行反转结果的映射，
    这种情况显然是一一对应的
        枚举了第一行就约等于枚举整个棋盘
    */
    for (int j=0;j<n-1;++j) {
        for (int k=0;k<m;++k) {
            if (a[j][k]!=tar) {
                step++;
                reverse(j+1,k);
            }
        }
    }
    for (int j=0;j<m;++j) {
        if (a[n-1][j]!=tar)return inf;
    }
    return step;
}
int main() {
    js;cin>>n>>m;
    forn(i,n) {//这里输入格式没注意，找了一圈才发现TVT也可以用scanf控制读取
        string s;cin>>s;
        forn(j,m) {
            b[i][j]=s[j]-'0';
        }
    }
    ll ans=inf;
    for (int i=0;i<(1<<m);++i) {
        ans=min(ans,solve(i,1));
        ans=min(ans,solve(i,0));
    }
    if (ans==inf)cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
    return 0;
}