Cod sursa(job #182205)

Utilizator alexeiIacob Radu alexei Data 20 aprilie 2008 15:02:28
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#define nmax 20

int a[nmax][nmax];
int n,m;
int solfin;

void change_1(int linie)
{int i;
	for(i=1; i<=m; ++i)
		a[linie][i]*=-1;
}
void change_2(int col)
{
int i;
	for(i=1; i<=n; ++i)
		a[i][col]*=-1;
}

void back_2(int col)
{
	if(col==m+1)
	{
		int sum=0,i,j;
		for(i=1; i<=n; ++i)
			for(j=1; j<=m; ++j)
				sum+=a[i][j];
			
			if(sum>solfin)
				solfin=sum;
	 return;
	}	
	
	back_2(col+1);
	
	change_2(col);
	
	back_2(col+1);
	
}
void back_1(int linie)
{
	if( linie==n+1)
	 {
		int sum=0,i,j;
		for(i=1; i<=n; ++i)
			for(j=1; j<=m; ++j)
				sum+=a[i][j];
			
			if(sum>solfin)
				solfin=sum;
	 return;
	 }
	back_2(1);		
	
	back_1(linie+1);
	
	change_1(linie);
	
	back_2(1);
	
	back_1(linie+1);
}
int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	int i,j;
	
	for(i=1; i<=n; ++i)
		for(j=1; j<=m; ++j)
			scanf("%d",&a[i][j]);
	
	back_1(1);
	
	printf("%d\n",solfin);
	
	
	return 0;
}