Cod sursa(job #260181)

Utilizator carbonixVictor Carbune carbonix Data 16 februarie 2009 19:10:56
Problema Jocul Flip Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 1.06 kb
/*
 * flip.c
 *
 *  Created on: Feb 16, 2009
 *      Author: scythe
 */

#include <stdio.h>

int n, m, semn_l[16], semn_c[16]; long int mat[16][16], max;
FILE *fin, *fout;

void readInput(){
	int i, j;
	fscanf(fin, "%d %d", &n, &m);
	for ( i = 0; i < n; i++ )
		for ( j = 0; j < m; j++ )
			fscanf(fin, "%ld", &mat[i][j]);

}

void columns(){
	int i, j;
	long int suma1 = 0, suma2 = 0;
	for ( j = 0; j < m; j++ ){
		semn_c[j] = 1;
		for ( i = 0; i < n; i++ )
			suma1 += semn_l[i] * semn_c[j] * mat[i][j];
		if(suma1 < 0) semn_c[j] = -1;
	}
}

long int sum(){
	long int suma = 0; int i, j;
	for ( i = 0; i < n; i++ )
		for ( j = 0; j < m; j++ )
			suma += semn_l[i] * semn_c[j] * mat[i][j];
	return suma;
}

void bkt(int k){
	long int suma;
	if( k == n ){
		columns();
		suma = sum();
		if ( suma > max )
			max = suma;
//		printf("%ld ", suma);
		return;
	}
	semn_l[k] = 1;  bkt(k+1);
	semn_l[k] = -1; bkt(k+1);
}

int main(){
	fin = fopen("flip.in", "r"); fout = fopen("flip.out", "w");
	readInput();
	bkt(0);
	fprintf(fout, "%ld\n", max);
	fclose(fin); fclose(fout);
	return 0;
}