Cod sursa(job #257794)

Utilizator f.v.antonFlavius Anton f.v.anton Data 13 februarie 2009 23:25:35
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream.h>
#include <conio.h>
#include <iostream.h>
int n,m,x[20],matr[17][17];long max=-1000000000;
long sum()
{        long s=0;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	    s+=matr[i][j];
	return s;
}
void invlin(int lin)
{
	for(int j=1;j<=m;j++)
	  matr[lin][j]*=-1;

}
void invcol(int col)
{

	for(int i=1;i<=n;i++)
	  matr[i][col]*=-1;

}
void tipar(int p)
{
	for(int i=1;i<=p;i++)
	 invlin(x[i]);
	if(sum()>max)
	 max=sum();
	for(int j=1;j<=m;j++)
	{
	 invcol(j);
	 if(sum()>max)
	  { max=sum();

	   }
	invcol(j);

	}
	for(i=1;i<=p;i++)
	 invlin(x[i]);

}

int valid(int k)
{
	for(int i=1;i<k;i++)
	  if(x[i]>=x[k])
	    return 0;
	return 1;
}

void back(int k,int p)
{
	for(int i=1;i<=n;i++)
	{	x[k]=i;
		if(valid(k))
		{
			if(k==p)
			 tipar(p);
			 else
			   back(k+1,p);
		}
	}
}

int main()
{
	clrscr();
	fstream f("flip.in",ios::in),g("flip.out",ios::out);
	f>>n>>m;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	     f>>matr[i][j];
	for(i=1;i<=n;i++)
	  back(1,i);
	if(sum()>max)
	 max=sum();
	g<<max;

	f.close();
	g.close();
	return 0;
}