Cod sursa(job #1870276)

Utilizator loghin.alexandruLoghin Alexandru loghin.alexandru Data 6 februarie 2017 15:38:32
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb

#include <fstream>
#include <vector>

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

std::vector<std::vector<int>> table;
std::vector<int> line;

#define MAX 17

long long outputsum;

int n, m;
int linesum;
int columnsum;
int i, j;


void backTrack(std::vector<std::vector<int>> table, long long sum, bool which, int i, int j)
{
	if (sum>outputsum)
	{
		outputsum = sum;
		if (which == 0)
		{
			for (auto j = 0; j < m; j++)
			{
				table[i][j] = -table[i][j];
			}
		}
		else
		{
			for (auto j = 0; j < n; j++)
			{
				table[j][i] = -table[j][i];
			}
		}

	}

	else
	{
		if (sum<outputsum)
		{
			return;

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

		if (-linesum > linesum)
		{
			backTrack(table, sum + (-linesum) - linesum, 0, i, j);

		}
	}

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

		if (-columnsum > columnsum)
		{
			backTrack(table, sum + (-columnsum) - columnsum, 1, i, j);

		}
	}


}



int main(void)
{
	long long sum = 0;
	fin >> n >> m;
	for (auto i = 0; i < n; i++)
	{
		line.clear();
		for (auto j = 0; j < m; j++)
		{
			int x;
			fin >> x;
			line.push_back(x);
			sum += x;
		}
		table.push_back(line);
	}
	outputsum = sum;
	backTrack(table, sum, 0, 0, 0);

	fout << outputsum;

}