Cod sursa(job #1870178)

Utilizator loghin.alexandruLoghin Alexandru loghin.alexandru Data 6 februarie 2017 14:14:57
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb

#include <fstream>

std::ifstream fin("flip.in");
std::ofstream fout("flip.out");

#define MAX 17

long long outputsum;

int n, m;
int linesum;
int columnsum;

void backTrack(int table[MAX][MAX], long long sum)
{
	if (sum>outputsum)
	{
		outputsum = sum;
	}

	for (auto i = 0; i < n; i++)
	{
		linesum = 0;
		for (auto j = 0; j < m; j++)
		{
			linesum += table[i][j];
		}

		if (-linesum > linesum)
		{
			for (auto j = 0; j < m; j++)
			{
				table[i][j] = -table[i][j];
			}
			sum = sum + (-linesum) - linesum;
			 backTrack(table, sum);
		}
	}

	for (auto i = 0; i < m; i++)
	{
		columnsum = 0;
		for (auto j = 0; j < n; j++)
		{
			columnsum += table[j][i];
		}

		if (-columnsum > columnsum)
		{
			for (auto j = 0; j < n; j++)
			{
				table[j][i] = -table[j][i];
			}
			sum = sum + (-columnsum) - columnsum;
			return backTrack(table, sum);
		}
	}


}
	
int main(void)
{
	long long sum = 0;
	fin >> n >> m;
	int table[MAX][MAX] = {};
	for (auto i = 0; i < n; i++)
	{
		for (auto j = 0; j < m; j++)
		{
			fin >> table[i][j];
			sum += table[i][j];
		}
	}
	outputsum = sum;
	backTrack(table, sum);

	fout << outputsum;

}