Cod sursa(job #1433650)

Utilizator Salomia_Adrian_325CCSalomia Adrian Salomia_Adrian_325CC Data 9 mai 2015 17:28:12
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>

void calcul_suma_l(int **m, long *s, int k, int M) {
	*s = 0;
	int i;
	for(i = 0;i < M;i++) 
		*s = *s - 2*m[k][i];
}

void calcul_suma_c(int **m, long *s, int k, int N, int *l) {
	*s = 0;
	int i;
	for(i = 0;i < N; i++) {
		if(l[i] == 0)
			*s = *s -2*m[i][k];
		else
			*s = *s +2*m[i][k];
	}
}

void bkt_c(long *suma_max, int **m, int suma, int *l, int N, int k, int *c, int M) {
	int i;
	for(i = 0;i < 2;i++) {
		c[k] = i;
		long suma_aux = 0;
		if(i == 1) {
			calcul_suma_c(m, &suma_aux, k, N, l);
		}
		if(k == M+1) {
			if(*suma_max < suma+suma_aux)
				*suma_max = suma+suma_aux;
		}
		else {
			bkt_c(suma_max, m, suma + suma_aux, l, N, k+1, c, M);
		}
	}


}

void bkt_l(long *suma_max, int **m, long suma, int k, int *l, int N, int *c, int M) {
	int i;
	for(i = 0;i < 2;i++) {
		l[k] = i;
		long suma_aux = 0;
		if(i == 1) 
			calcul_suma_l(m, &suma_aux, k, M);
		if(k == N-1) {
			bkt_c(suma_max, m, suma+suma_aux, l, N, 0, c, M);
		}
		else {
			bkt_l(suma_max, m, suma+suma_aux, k+1, l, N, c, M);
		}
	}
}

int main() {
	FILE *f1 = fopen("flip.in", "r");
	FILE *f2 = fopen("flip.out", "w");	
	int N, M;
	fscanf(f1, "%d%d", &N, &M);

	int i, j;
	int **m = (int **) malloc (N * sizeof(int*));
	for (i = 0; i < N; i++) {
		m[i] = (int *) malloc (M *sizeof(int));
	}

	long suma = 0;
	for(i = 0;i < N;i++)
		for(j = 0;j < M;j++) {
			fscanf(f1, "%d", &m[i][j]);
			suma += m[i][j];
		}

	long suma_max = suma;
	int *l = (int *) malloc (N * sizeof(int));
	int *c = (int *) malloc (M * sizeof(int));
	bkt_l(&suma_max, m, suma, 0, l, N, c, M);

	fprintf(f2, "%d\n", suma_max);

	fclose(f1);
	fclose(f2);
	return 0;
}