Cod sursa(job #865048)

Utilizator leif.lazarDe Sters leif.lazar Data 25 ianuarie 2013 23:15:05
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<fstream>

using namespace std;

int width, height;
int* switches;
int** matrix;

void sum(int column, int& maxSum)
{
	if(column == width - 1)
	{
		int matrixSum = 0;

		for(int i = 0; i < height; i++)
		{
			int rowSum = 0;

			for(int j = 0; j < width; j++)
			{
				rowSum += matrix[i][j] * switches[j];
			}

			matrixSum += rowSum > -rowSum ? rowSum : -rowSum;
		}

		if(matrixSum > maxSum)
		{
			maxSum = matrixSum;
		}
	}
	else
	{
		switches[column] = -1;
		sum(column + 1, maxSum);
		switches[column] = 1;
		sum(column + 1, maxSum);
	}
}

int main()
{
	int maxSum = 0;
	ifstream inputFile;
	ofstream outputFile;

	inputFile.open("flip.in");

	inputFile>>height;
	inputFile>>width;

	matrix = new int*[height];

	for(int i = 0; i < height; i ++)
	{
		matrix[i] = new int[width];

		for(int j = 0; j < width; j++)
		{
			inputFile>>matrix[i][j];
		}
	}

	inputFile.close();

	switches = new int[width];

	for(int i = 0; i < width; i ++)
	{
		switches[i] = 1;
	}

	sum(0, maxSum);

	for(int i = 0; i < height; i ++)
	{
		delete[] matrix[i];
	}

	delete[] matrix;
	delete[] switches;

	outputFile.open("flip.out");
	outputFile<<maxSum;

	outputFile.close();

	return 0;
}