Cod sursa(job #1707195)

Utilizator dalavricDaniel Lavric dalavric Data 24 mai 2016 16:21:31
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <math.h>

int n, m, maxSum,min;
int flip[16];
int aux[16][16];
int matrix[16][16];


void flipColumn(int j, int n)
{
	for (int i = 0; i < n; i++)
	{
		matrix[i][j] = 0 - matrix[i][j];
	}
}

void calculateSum()
{
	int sum = 0;
	int lineSum = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			matrix[i][j] = aux[i][j] * flip[i];
	}

	for (int j = 0; j < m; j++)
	{
		int positiveSum = 0;
		int negativeSum = 0;
		for (int i = 0; i < n; i++)
		{
			if (matrix[i][j] < 0)
			{
				negativeSum += matrix[i][j];
			}
			else
			{
				positiveSum += matrix[i][j];
			}
		}
		if (abs(negativeSum) > positiveSum)
		{
			flipColumn(j, n);
		}
	}

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

		for (int j = 0; j < m; j++)
		{
			sum += matrix[i][j];
		}

	}

	if (sum > maxSum)
	{
		maxSum = sum;
	}


}



void backTracking(int k)
{
	if (k == min)
	{
		calculateSum();
		return;
	}

	for (int i = -1; i<2; i += 2)
	{
		flip[k] = i;
		backTracking(k + 1);
	}

}

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

	fscanf(f, "%d", &n);
	fscanf(f, "%d", &m);
	if (n < m)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				fscanf(f, "%d", &aux[i][j]);
			}
		}
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				fscanf(f, "%d", &aux[j][i]);
			}
		}
		int aux = n;
		n = m;
		m = aux;
	}

	maxSum = 0;
	if (n < m)
	{
		min = n;
	}
	else min = m;

	backTracking(0);

	fprintf(g,"%d", maxSum);

	fclose(g);
	fclose(f);
	return 0;
}