Cod sursa(job #514685)

Utilizator tvararuVararu Theodor tvararu Data 19 decembrie 2010 13:05:08
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <iostream>
using namespace std;
int g_nVerSize, g_nHorSize;
long int g_lnMatrix[16][16], g_lnMax = 0;

void FlipColon (const int &rnIndex)
{
	for (int iii = 0; iii < g_nVerSize; iii++)
		g_lnMatrix[iii][rnIndex] *= -1;
}

void FlipLine (const int &rnIndex)
{
	for (int iii = 0; iii < g_nHorSize; iii++)
		g_lnMatrix[rnIndex][iii] *= -1;
}

bool CheckLine (const int &rnIndex)
{
	long int lnSum = 0;
	for (int iii = 0; iii < g_nHorSize; iii++)
		lnSum += g_lnMatrix[rnIndex][iii];
	if (lnSum >= 0) return false;
	return true;
}

long int CalculateSum ()
{
	long int lnSum = 0;
	for (int iii = 0; iii < g_nVerSize; iii++)
		for (int jjj = 0; jjj < g_nHorSize; jjj++)
			lnSum += g_lnMatrix[iii][jjj];
	return lnSum;
}

void Backtrack (int nVerIndex, int nHorIndex)
{
	if (nVerIndex == g_nVerSize)
	{
		long int lnSum = CalculateSum ();
		if (lnSum > g_lnMax)
			g_lnMax = lnSum;
	}
	else if (nHorIndex == g_nHorSize)
	{
		if (CheckLine (nVerIndex)) FlipLine (nVerIndex);
		Backtrack (nVerIndex + 1, nHorIndex);
	}
	else
	{
		Backtrack (nVerIndex, nHorIndex + 1);
		FlipColon (nHorIndex);
		Backtrack (nVerIndex, nHorIndex + 1);		
	}
}

int main ()
{
	ifstream in ("flip.in");
	in >> g_nVerSize >> g_nHorSize;
	for (int iii = 0; iii < g_nVerSize; iii++)
		for (int jjj = 0; jjj < g_nHorSize; jjj++)
			in >> g_lnMatrix[iii][jjj];
	in.close();
	
	Backtrack (0, 0);

	ofstream out ("flip.out");
	out << g_lnMax;
	out.close();
	
	return 0;
}