Cod sursa(job #133305)

Utilizator xtephanFodor Stefan xtephan Data 8 februarie 2008 10:21:49
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
/*
flip
infoarena
back-tracking
*/
#include<stdio.h>


long a[16][16], n,m;
long smax; /*suma maxima*/
int c[16]; /*caract*/

void cit();
void back(int k);
void afis();


int main() {

	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);

	cit();
	back(0);
	afis();

	return 0;
}



void cit() {

	scanf("%ld %ld", &n, &m);

	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j)
			scanf("%ld", &a[i][j]);

}



void back(int k) {

	int i,j;
	long s,t;

	if(k==m) {

		s=0;

		for(i=0; i<n; ++i) {

			t=0;
			for(j=0; j<m; ++j)
				if(c[j]) /*-1 pe coloana*/
					t+=-a[i][j];
				else
					t+=a[i][j];

			if(t>-t)  /*-1 pe linie*/
				s+=t;
			else
				s+=-t;

		}

		if(s>smax)
			smax=s;
		return;
	}


	c[k]=0;
	back(k+1);
	c[k]=1;
	back(k+1);
}


void afis() {
	printf("%ld", smax);
}