C++(g++ 7.5.0) 解法, 执行用时: 33ms, 内存消耗: 500K, 提交时间: 2023-07-10 11:02:22

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10,M=20;
int g[N][M];
int n,m;
int d[N][M];
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

void overturn(int x,int y)
{
	d[x][y]=!d[x][y];
	for(int i=0;i<4;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if(tx<0||tx>=n||ty<0||ty>=m) continue;
		d[tx][ty]=!d[tx][ty];
	}
}

int solve(int state,int ed)
{
	memcpy(d,g,sizeof g);
	int cnt=0;
	for(int i=0;i<m;i++)
		if((state>>i)&1)
		{
			cnt++;
			overturn(0,i);
		}
	for(int i=1;i<n;i++)
		for(int j=0;j<m;j++)
			if(d[i-1][j]!=ed)
			{
				cnt++;
				overturn(i,j);
			}
	for(int i=0;i<m;i++)
		if(d[n-1][i]!=ed)
			return 2e9;
	return cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{
			char c;
			cin>>c;
			g[i][j]=c-'0';
		}
	int res=2e9;
	for(int i=0;i<(1<<m);i++)
	{
		res=min(res,solve(i,0));
		res=min(res,solve(i,1));
	}
	if(res==2e9) cout<<"Impossible"<<endl;
	else cout<<res<<endl;
	return 0;
}

C++ 解法, 执行用时: 31ms, 内存消耗: 456K, 提交时间: 2022-07-11 15:14:10

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
int n,m,ans=1000;
int a[105][11],now[105][11];
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
int calc(int state,int pd);
void turn(int in,int im);
int main(){
	cin>>n>>m;
	for(int i=1;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,min(calc(i,0),calc(i,1)));
	if(ans!=1000)cout<<ans<<endl;
	else cout<<"Impossible"<<endl;
     return 0;
}
void turn(int in,int im){
	for(int i=0;i<=4;i++){
		int a=in+dx[i],b=im+dy[i];
		if(a>=1&&a<=n&&b>=0&&b<m)
		now[a][b]^=1;
	}
}
int calc(int state,int pd){
	int res=0;
	for(int i=1;i<=n;i++)
	for(int j=0;j<m;j++)
	now[i][j]=a[i][j];
	for(int i=0;i<m;i++)
	if(state&(1<<i))
	turn(1,i),res++;
	for(int i=2;i<=n;i++)
	for(int j=0;j<m;j++)
	if(now[i-1][j]!=pd)
	turn(i,j),res++;
	for(int i=0;i<m;i++)
	if(now[n][i]!=pd)
	return 1000;
	return res;
}