Cod sursa(job #223748)

Utilizator adelinavVidovici Adelina adelinav Data 29 noiembrie 2008 12:36:31
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
int smax,n,m,a[20][20],st[20],spoz[20],sneg[20],flip[20];

void solutie(){
	int sc=0,dif,i,j;
	for(i=1;i<=n;i++)
		if(flip[i]!=st[i]){
			for(j=1;j<=m;j++)
			if(a[i][j]>0){
				spoz[j]-=a[i][j];
				a[i][j]=-a[i][j];
				sneg[j]+=a[i][j];
			}
			else{
				sneg[j]-=a[i][j];
				a[i][j]=-a[i][j];
				spoz[j]+=a[i][j];
			}
			flip[i]=1-flip[i];
		}
	for(i=1;i<=m;i++){
		dif=spoz[i]+sneg[i];
		if(dif>0) sc+=dif;
		else sc+=-dif;
	}
		if(sc>smax) smax=sc;
}

void bkt(int k){
	if(k==n+1) solutie();
	else{
		st[k]=-1;
		while(st[k]<1){
			st[k]++;
			bkt(k+1);
		}
	}
}

int main(){
int i,j;
freopen("flip.in","r",stdin);
freopen("flip.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
	for(j=1;j<=m;j++){
		scanf("%d",&a[i][j]);
		if(a[i][j]>0) spoz[j]=spoz[j]+a[i][j];
		else sneg[j]=sneg[j]+a[i][j];
	}

bkt(1);
printf("%d",smax);
return 0;
}