Cod sursa(job #1652)

Utilizator Omega91Nicodei Eduard Omega91 Data 14 decembrie 2006 10:45:57
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <fstream>
using namespace std;
ifstream f1("flip.in");
ofstream f2("flip.out");
long int tabla[17][17], slin[17], scol[17], stotal, stotalmax=-1000000;
int n,m; //nr de ljnii="n" shi coloane="m"
//ideea e sa aflam cea mai mica suma d pe o coloana shi o inmultim cu -1 astfel devine pozitiva.
//apoi refacem sumele shi vedem care linie sau coloana este cea mai mica shi daca schimband-o, suma totala devine
//mai mare.
int clearall() //reinitializeaza scol, slin, stotal
{
	 int i;
	 stotal=0;
	 for (i=1; i<=n; i+=1)
		  slin[i]=0;
	 for (i=1; i<=m; i+=1)
		  scol[i]=0;
	 return 0;
}
int makesums() //face sumele pt alea d mai sus :)
{
	 int i,j;
	 for (i=1; i<=n; i+=1)
		  for (j=1; j<=m; j+=1)
		  {
				slin[i]+=tabla[i][j];   //calc suma pt linii
				stotal+=tabla[i][j];    //calc suma totala pe tabla
		  }
	 for (j=1; j<=m; j+=1)
		  for (i=1; i<=n; i+=1)
				scol[j]+=tabla[i][j];   //calc suma pt coloane

	 if (stotal>stotalmax) stotalmax=stotal;
	 return 0;
}
int maxlin() //det. maximul negativ p o linie
{
	 int aux=-1,i;
	 long int max;
	 max=0;
	 for (i=1; i<=n; i+=1)
		  if (slin[i]<max)    //practic se afla minimul care este cel mai mare nr negativ
		  {
				max=slin[i];
				aux=i;          //stocheaza pozitia liniei p care se afla cea mai mica suma
		  }
	 return aux;
}
int maxcol() //det. maximul negativ p o coloana
{
	 int aux=-1,i;
	 long int max;
	 max=0;
	 for (i=1; i<=m; i+=1)
		  if (scol[i]<max)    //tot la fel k mai sus
		  {
				max=scol[i];
				aux=i;
		  }
	 return aux;
}
int citire() //face citirea din fisier
{
	 int i,j;
	 f1>>n>>m;
	 for (i=1; i<=n; i++)
		  for (j=1; j<=m; j++)
				f1>>tabla[i][j];
	 return 0;
}
int main(void)
{
	 int cpos, lpos,i;
	 long int maxscol, maxslin;
	 citire();
	 bool gata;
	 gata=false;
	 while (!gata)
	 {
		  makesums();
		  gata=true;
		  lpos=maxlin();
		  cpos=maxcol();
		  maxslin=slin[lpos];
		  maxscol=scol[cpos];
		  if (maxscol<=maxslin && (lpos!=-1 || cpos!=-1))
		  {
				gata=false;
				for (i=1; i<=n; i+=1)
					 tabla[i][cpos]=tabla[i][cpos]*(-1);
		  }
		  if (maxslin<=maxscol && (lpos!=-1 || cpos!=-1) && gata)
		  {
				gata=false;
				for (i=1; i<=m; i+=1)
					 tabla[lpos][i]=tabla[lpos][i]*(-1);
		  }
		  clearall();
	 }
	 makesums();
	 f2<<stotalmax<<endl;
	 f1.close();
	 f2.close();
	 return 0;
}