speed_solve.c

#include<stdio.h>
#include<string.h>
int n,m,table[20],Fill,Maxima,Answer;

int count_bin(int a){
	int res=0;
	while(a>0){
		res+=a&1;
		a>>=1;
	}
	return res;
}

int put_solution(int *solution){
	int i,j;
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			printf("%d ",solution[i]&1);
			solution[i]>>=1;
		}
		puts("");
	}
	return 1;
}

void solve(int a,int b){
	int i,table_copy[20],solution[20],sum=0;
	memcpy(table_copy,table,sizeof(table));
	table_copy[0]^=Fill&(a^(a>>1)^(a<<1));
	table_copy[1]^=a;
	solution[0]=a;
	sum+=count_bin(a);
	for(i=1;i<m;i++){
		solution[i]=Fill^table_copy[i-1];
		table_copy[i-1]=Fill;
		table_copy[i]^=Fill&(solution[i]^(solution[i]>>1)^(solution[i]<<1));
		if(i<m-1)table_copy[i+1]^=solution[i];
		sum+=count_bin(solution[i]);
	}
	if(table_copy[m-1]==Fill && sum<=Maxima){
		Maxima=sum;
		Answer=a;
		if(b!=0)put_solution(solution);
	};
}


int main(){
	int i,j,k,l;
	memset(table,0,sizeof(table));
	scanf("%d%d",&n,&m);
	Maxima=n*m;
	Fill=(1<<n)-1;
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			table[i]<<=1;
			scanf("%d",&l);
			table[i]+=l;
		}
	}
	for(i=0;i<1<<m;i++){
		solve(i,0);
	}
	printf("\n%d steps\n",Maxima);
	solve(Answer,1);
	return 0;
}