Cod sursa(job #132889)

Utilizator swift90Ionut Bogdanescu swift90 Data 6 februarie 2008 20:50:24
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
int n,m,nr[17][17],lin[17],col[17],sol[17],smax,si,sc,s;
void prel(){
	int i,j;
	s=si;
	for(i=1;i<=m;++i){
		if(sol[i]==1)
			s-=2*col[i];
	}
	if(s>smax)
		smax=s;
	sc=s;
	for(i=1;i<=n;++i){
		s-=2*lin[i];
		for(j=1;j<=m;++j){
			if(sol[j]==1)
				s+=nr[i][j]<<2;
		}
		if(s>sc)
			sc=s;
		else
			s=sc;
	}
	if(sc>smax)
		smax=sc;
}
void back(int k){
	if(k==m+1)
		prel();
	else{
		sol[k]=-1;
		while(sol[k]<1){
			++sol[k];
			back(k+1);
		}
	}
}
int main(){
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j){
			scanf("%d",&nr[i][j]);
			s+=nr[i][j];
		}
	}
	si=s;
	smax=s;
	for(i=1;i<=m;++i){
		for(j=1;j<=n;++j)
			col[i]+=nr[j][i];
	}
	for(i=1;i<=n;++i){
		for(j=1;j<=m;++j)
			lin[i]+=nr[i][j];
	}
	
	back(1);
	
	printf("%d\n",smax);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}