Cod sursa(job #66548)

Utilizator plastikDan George Filimon plastik Data 19 iunie 2007 19:01:49
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
// flip, infoarena
// avand o matrice cu numere trebuie obtinuta suma maxima; matricea are 16 linii si 16 coloane max.
// se pot comuta (inmulti cu -1) coloane sau linii
// generez toate modurile de a comuta linii
// comut acele coloane care prin comutare dau o suma mai mare

#include <cstdio>
#include <cmath>

const int MAX_N = 16;
int A[MAX_N][MAX_N],B[MAX_N][MAX_N],  M, N, bsum = 0;

bool com[MAX_N];

void check(void) {
	int sum = 0, ysum, nsum, i, j, c;
	for (i = 0; i < M; ++ i) 
		for (j = 0; j < N; ++ j) {
			B[i][j] = A[i][j];
			if (com[i] == 1)
				B[i][j] = -B[i][j];
		}
	for (j = 0; j < N; ++ j) {
		ysum = nsum = 0;
		for (i = 0; i < M; ++ i) {
			ysum -= B[i][j];
			nsum += B[i][j];
		}
		if (ysum > nsum)
			sum += ysum;
		else sum += nsum;
	}
	if (sum > bsum)
		bsum = sum;
}

void make_switches(void) {
	// comutatoarele le pun in com[]
	int i, j,
	    p2 = (int)pow(2, M); // 2 ^ M pentru ca voi comuta liniile
	for (i = 0; i < p2; ++ i) {
		for (j = 0; j < M; ++ j)
			if (i & (1 << j)) 
				com[j] = 1;
			else
				com[j] = 0;
		check();
	}
}

int main(void) {
	FILE *in = fopen("flip.in", "r"),
	     *out = fopen("flip.out", "w");

	fscanf(in, "%d %d", &M, &N);
	int i, j;
	for (i = 0; i < M; ++ i)
		for (j = 0; j < N; ++ j)
			fscanf(in, "%d", &A[i][j]);
	fclose(in);

	make_switches();

	fprintf(out, "%d\n", bsum);
	fclose(out);

	return 0;
}