Cod sursa(job #618524)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 15 octombrie 2011 17:44:22
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb

#include<stdio.h>

int lin,col;
int sumaMax = -1<<29, sumaInitiala;
int sumaLin[20],sumaCol[20];
int 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, i, j;
	
	freopen("flip.in", "r", stdin);
		scanf("%d %d", &lin, &col);
		for (i=1;i<=lin;i++)
			for (j=1;j<=col;j++)
				scanf("%d", &a[i][j]);
	fclose(stdin);
	
	CalculeazaSumeInitiale();
	
	for (k=1;k<=lin+col-1;k++)
		Back(1,k);
	
	freopen("flip.out", "w", stdout);
		printf("%d\n", sumaMax);
	fclose(stdout);
	
	return 0;
}