深搜76pts,wa#9#11,RE#8求助
查看原帖
深搜76pts,wa#9#11,RE#8求助
421265
eastcloud楼主2022/5/12 21:30
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,map[200][200],map2[200][200],map3[200][200],map4[200][200];
void flip(int x,int y){
	map[x-1][y]^=1;
	map[x][y-1]^=1;
	map[x+1][y]^=1;
	map[x][y+1]^=1;
	map[x][y]^=1;
}
int tot;
bool tr(int x){
	for(int o=1;o<=m;o++){
		if(map[x-1][o]){
			map3[x][o]=1;
			tot++;
		}
		if(map[x-1][o])flip(x,o);
	}
	if(x==n){
		for(int o=1;o<=m;o++)if(map[x][o]) return false;
		return true;
	}
	else return tr(x+1);
}
int main(){
	char x;
	cin>>n>>m;
	int ans=(1<<30);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>map[i][j];
	for(int i=0;i<(1<<m);i++){
		for(int k=1;k<=n;k++) for(int j=1;j<=m;j++)map2[k][j]=map[k][j];
		int tmp=i;
		for(int j=1;j<=m;j++){
			if(tmp & 1){
				flip(1,j);
				map3[1][j]=1;
				tot++;
			}
			tmp>>=1;
		}
		if(tr(2)){
			if(ans>tot){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=m;j++){
						map4[i][j]=map3[i][j];
					}
				}
				ans=tot;
			}
		}
		memset(map3,0,sizeof(map3));
		tot=0;
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)map[i][j]=map2[i][j];
	}
	if(tot==(1<<30))cout<<"IMPOSSIBLE";
	else{
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cout<<map4[i][j]<<' ';
			}
			cout<<endl;
		}
	}
}
2022/5/12 21:30
加载中...