n = 3 n=3 n=3 时,状压dp,用二进制表示每一列的情况, d p [ i ] [ j ] dp[i][j] dp[i][j] 表示第 i i i 列变成状态 j j j 的最小操作数,转移方程 d p [ i ] [ j ] = min ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] + c h a n g e ( i , j ) ) dp[i][j]=\min(dp[i][j],\ dp[i-1][k]+change(i, j)) dp[i][j]=min(dp[i][j],dp[i−1][k]+change(i,j)) (如果 k k k 和 j j j 状态合法)
#include<bits/stdc++.h>usingnamespace std;#defineintlonglongusing i64 =longlong;typedef pair<int,int> PII;typedef pair<int,char> PIC;typedef pair<double,double> PDD;typedef pair<int, PII> PIII;typedef pair<int, pair<int,bool>> PIIB;constint N =1e6+10;constint maxn =1e6+10;constint mod =1e9+7;constint mod1 =954169327;constint mod2 =906097321;constint INF =0x3f3f3f3f3f3f3f3f;voidsolve(){int n, m;
cin >> n >> m;
vector<vector<char>>g(n +1,vector<char>(m +1));for(int i =1; i <= n; i ++)for(int j =1; j <= m; j ++)
cin >> g[i][j];if(n >=4) cout <<-1<<'\n';elseif(n ==1) cout <<0<<'\n';elseif(n ==2){
vector<int>cnt(m +1);for(int i =1; i <= m; i ++){int tmp =0;for(int j =1; j <= n; j ++){if(g[j][i]=='1') tmp ++;}
cnt[i]= tmp;}
vector<int>ans(3);for(int k =0; k <3; k ++){
ans[k]+=abs(cnt[1]- k);int lst = k;for(int i =2; i <= m; i ++){if(lst &1){if(cnt[i]&1) ans[k]++;
lst =0;}else{if(cnt[i]%2==0) ans[k]++;
lst =1;}}}
cout <<min({ans[0], ans[1], ans[2]})<<'\n';}elseif(n ==3){// 将每一列转化成二进制
vector<int>mp(m +1);for(int i =1; i <= m; i ++){int tmp =0;for(int j =1; j <= n; j ++){if(g[j][i]=='1') tmp +=(1ll<<(j -1));}
mp[i]= tmp;}// 转化步数auto change =[&](int a,int b){int state =(a ^ b);int ans =0;for(int i =0; i <3; i ++){if((state >> i)&1) ans ++;}return ans;};// 判断相邻状态合法性auto check =[&](int a,int b){int a1 =((a >>0)&1), a2 =((a >>1)&1), a3 =((a >>2)&1);int b1 =((b >>0)&1), b2 =((b >>1)&1), b3 =((b >>2)&1);if((a1 + a2 + b1 + b2)%2==0)returnfalse;if((a2 + a3 + b2 + b3)%2==0)returnfalse;returntrue;};// 初始化
vector<vector<int>>dp(m +1,vector<int>(8, INF));for(int i =0; i <8; i ++) dp[1][i]=change(mp[1], i);for(int i =2; i <= m; i ++){for(int j =0; j <8; j ++)// i-1列的状态{for(int k =0; k <8; k ++)// i列的状态{if(!check(j, k))continue;// jk作为相邻状态不合法
dp[i][k]=min(dp[i][k], dp[i -1][j]+change(mp[i], k));}}}int ans = INF;for(int i =0; i <8; i ++) ans =min(ans, dp[m][i]);if(ans == INF) cout <<-1<<'\n';else cout << ans <<'\n';}}signedmain(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);int t =1;// cin >> t;while(t--){solve();}}