Cod sursa(job #618472)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 15 octombrie 2011 17:27:04
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include<fstream>

using namespace std;
ofstream fout("flip.out");
	
long lin,col, sumaMax = -1<<29, sumaInitiala;
long sumaLin[20],sumaCol[20];
long a[20][20];

inline int SumaLin(int i)
{
	int s=0;
	for (int j=1;j<=col;j++)
		s+=a[i][j];
	return s;
}

inline int SumaCol(int j)
{
	int s=0;
	for (int i=1;i<=lin;i++)
		s+=a[i][j];
	return s;
}

//Calc suma initiala pe fiecare linie, coloana si a intregii matrice
void CalculeazaSumeInitiale()
{
	int i;
	for (i=1;i<=lin;i++) sumaLin[i] = SumaLin(i);
	for (i=1;i<=col;i++) sumaCol[i] = SumaCol(i);
	for (i=1;i<=lin;i++) sumaInitiala += sumaLin[i];
	sumaMax = sumaInitiala;
}

int stivaIndici[40]; //punem indicii de la 1 la lin pentru linii si de la lin+1 la lin+col pentru coloane
int stivaSume[40]; //punem suma initiala corespunzatoare liniei sau coloanei reprezentata in stivaIndici

//un candidat este valid pentru a fi pus pe stiva daca este mai mare decat ultimul element adaugat
bool EValid(int top, int candidat)
{
	if (top == 1) return true;
	if (candidat > stivaIndici[top - 1]) return true;
	return false;
}

//daca liniile si coloanele de pe stiva genereaza , prin flip, o suma mai mare, actualizeaza
void ActualizeazaMax(int k)
{
	int i, sumaTemp = sumaInitiala;
	for (i=1;i<=k;i++)
		sumaTemp += (-2) * stivaSume[i];
	if (sumaTemp > sumaMax) sumaMax = sumaTemp;
	
	/*
	for (i = 1; i <= k; i++) fout<<stivaSume[i]<<" ";
	fout<<"\t-->\t";
	for (i=1;i<=k;i++)
		fout<<stivaIndici[i]<<" ";
	fout<<"\t\t\t"<<sumaTemp<<"\n";
	*/
}

//Generam Combinari de lin+col luate cate k, k=1,lin+col-1
void Back(int top, int k)
{
	if (top == k+1) ActualizeazaMax(k);
	else 
	{
		int i;
		for (i=1;i<=lin+col;i++)
			if (EValid(top,i))
			{
				stivaIndici[top] = i;
				stivaSume[top] = i <= lin ? sumaLin[i]: sumaCol[i - lin];
				Back(top+1,k);
			}
	}
}

int main()
{
	int k;
	
	ifstream fin("flip.in");
		fin>>lin>>col;
		int i,j;
		for (i=1;i<=lin;i++)
			for (j=1;j<=col;j++)
				fin>>a[i][j];
	fin.close();
	
	CalculeazaSumeInitiale();
	
	for (k=1;k<=lin+col-1;k++)
		Back(1,k);
	
	fout<<sumaMax<<"\n";
	fout.close();
	
	return 0;
}