我是蒟蒻第一次写题解，希望这篇题解能给你帮助

核心解题思路

  1. 问题分析：由于每次操作会翻转自身及上下左右四个格子，且我们需要处理 的棋盘（ 可达 100， 最大为 10）。直接暴力枚举所有状态是不可能的，但 意味着可以用一个整数表示一行的状态（二进制压缩）。
  2. 关键策略：
    • 枚举第一行：第一行的操作方式决定了后续所有行的操作方式。第一行共有 种可能的操作状态（，即最多 1024 种），这是算法能运行不超时的关键。
    • 递推后续行：对于第 行，如果第 行的某个格子仍为白色（0），则必须在第 行的正下方位置进行翻转操作，才能将第 行的该位置变为黑色（1）。依此类推，逐行确定操作方案。
    • 检查最后一行：处理完所有行后，只需检查最后一行是否全部变为黑色。如果是，则找到一个可行解。
  3. 目标：分别计算将棋盘变为全黑和全白的最小操作次数，取两者中的较小值。
  4. 时间复杂度:O()

参考代码 (C++)

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=1e4+10;
int g[110][15];
int n,m;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
// 函数：计算将棋盘变为全x（1黑色,0白色）的最小操作次数
int cul(int x){
    int min_ops=INT_MAX;
  // 枚举第一行的所有操作状态 (0..2^m - 1)
    for(int mask=0;mask<(1<<m);mask++){
        int tmp[110][15];
        int ops=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                tmp[i][j]=g[i][j];
            }
        }
        //处理第一行的操作
        for(int j=1;j<=m;j++){
            if(mask&(1<<(j-1))){
                ops++;
              // 翻转第一行j列及其相邻格子
                for(int i=0;i<4;i++){
                    int a=dx[i]+1,b=dy[i]+j;
                    if(a<1||a>n||b<1||b>m) continue;
                    tmp[a][b]^=1;
                }
              //翻转自己
                tmp[1][j]^=1;
            }
        }
        //处理第2到第n行
        for(int i=2;i<=n;i++){
            for(int j=1;j<=m;j++){
                if (tmp[i - 1][j] == (1-x)) {//(1-x)意思是，如果要变成黑色1，那么要看哪个等于0；白色同理
                    ops++;
                    // 翻转当前行j列及其相邻格子
                    for (int d = 0; d < 4; d++) {
                        int ni = i + dx[d];
                        int nj = j + dy[d];
                        if (ni >= 1 && ni <= n && nj >= 1 && nj <= m) {
                            tmp[ni][nj] ^= 1;
                        }
                    }
                    // 自己也有被翻转 
                    tmp[i][j] ^= 1; 
                }
            }
        }
      // 检查最后一行是否全为x
        bool ok = true;
        for (int j = 1; j <= m; j++) {
            if (tmp[n][j] != x) {
                ok = false;
                break;
            }
        }
        if (ok) {
            if (ops < min_ops) {
                min_ops = ops;
            }
        }
    }
    return min_ops;
}
void solve() {
	cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char x;
            cin>>x;
            g[i][j]=x-'0';
        }
    }
    int ans=min(cul(1),cul(0));//看看哪个更小
    if(ans==INT_MAX){
        cout<<"Impossible"<<endl;
    }
    else{
        cout<<ans<<endl;
    }
	return;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t;
//	cin>>t;
	t=1;
	while(t--) {
		solve();
	}
}