Cod sursa(job #953643)

Utilizator deividFlorentin Dumitru deivid Data 26 mai 2013 21:35:37
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>

#define inf (1<<30)

FILE*f=fopen("flip.in","r");
FILE*g=fopen("flip.out","w");

int n,m,sol;
int A[17][17],B[17][17],x[17];

inline int max ( int a , int b ){
	if ( a >= b )	return a;
	return b;
}

inline void compara_solutie () {
	
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= m ; ++j ){
			B[i][j] = A[i][j];
		}
	}
	
	for ( int i = 1 ; i <= x[0] ; ++i ){
		int coloana = x[i];
		
		for ( int j = 1 ; j <= n ; ++j ){
			B[j][coloana] = -B[j][coloana];
		}
	}
	
	int s = 0;
	for ( int i = 1 ; i <= n ; ++i ){
		
		int s_linie = 0;
		for ( int j = 1 ; j <= m ; ++j ){
			s_linie += B[i][j];
		}
		if ( s_linie < 0 )	s_linie = -s_linie;
		
		s += s_linie;
	}
	
	sol = max(sol,s);
}

void back ( int niv ){
	
	if ( niv > m ){
		
		compara_solutie();
		
		return ;
	}
	
	++x[0]; x[x[0]] = niv;
	back(niv+1);
	x[x[0]] = 0; --x[0];
	
	back(niv+1);
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	for ( int i = 1 ; i <= n ; ++i ){
		for ( int j = 1 ; j <= m ; ++j ){
			fscanf(f,"%d",&A[i][j]);
		}
	}
	
	sol = -inf;
	back(1);
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}