Cod sursa(job #1747525)

Utilizator octavyan55Aurel Savoiu octavyan55 Data 25 august 2016 02:00:55
Problema Jocul Flip Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>
#include <stdlib.h>


int sum_elements(int** matrix, int n, int m)
{
	int i, j;
	int sum = 0;
	for (i = 0; i < n ;i++)
		for (j = 0; j < m ;j++)
			sum += matrix[i][j];
	return sum;
}

int flip_col(int **matrix, int n, int m, int sum, int c)
{
	for (int i = 0 ; i < n ; i ++)
	{
		sum = sum -  2 * matrix[i][c];
		matrix[i][c] = -1 * matrix[i][c];
	}
	return sum;
}

int flip_row(int **matrix, int n, int m, int sum, int r)
{
	for (int i = 0 ; i < m ; i ++)
	{
		sum = sum -  2 * matrix[r][i];
		matrix[r][i] = -1 * matrix[r][i];
	}
	return sum;
}

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

}

int backtrack_cols(int** matrix, int n, int m, int sum, int max_sum,int k)
{
	int tmp_sum;
	for (int i = k ; i < m ; i ++){
		tmp_sum = flip_col(matrix, n, m, sum, i);
		max_sum = max(tmp_sum, max_sum);
		max_sum = backtrack_cols(matrix, n, m, tmp_sum, max_sum, k + 1);
		tmp_sum = flip_col(matrix, n, m, sum, i);
	}
	return max_sum;
}

int backtrack_rows(int** matrix, int n, int m, int sum, int max_sum, int k)
{
	int tmp_sum;
	for (int i = k ; i < n ; i ++){
		tmp_sum = flip_row(matrix, n, m, sum, i);
		max_sum = max(tmp_sum, max_sum);
		max_sum = backtrack_cols(matrix, n, m, tmp_sum, max_sum, 0);
		max_sum = backtrack_rows(matrix, n, m, tmp_sum, max_sum, k + 1);
		tmp_sum = flip_row(matrix, n, m, sum, i);
	}
	return max_sum;
}


int main(int argc, char** argv)
{
	int n, m, i, j, sum;
	int **matrix;	
	FILE *in, *out;

	in = fopen("flip.in", "r");
	out = fopen("flip.out", "w");

	fscanf(in, "%d %d", &n, &m);

	// Initialize the matrix
	matrix = malloc(n * sizeof(int*));
	for (i = 0; i < n; i++)
		matrix[i] = malloc(m * sizeof(int));

	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			fscanf(in, "%d", &matrix[i][j]);

	// Calculate the initial sum
	sum = sum_elements(matrix, n , m);
	
	sum = backtrack_rows(matrix, n, m, sum, sum, 0);
	
		
	fprintf(out, "%d", sum);

	fclose(in);
	fclose(out);	
}