Cod sursa(job #226700)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 2 decembrie 2008 17:23:13
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream.h>

int st[17],n,m,k,as,ev,i,j,a[17][17],suma=0;

void init()
{	st[k]=-1;	}

int succ()
{
	if(st[k]<1)
	{
		st[k]++;
		return 1;
	}
	return 0;
}
int sol()
{
	return k==n;
}
int valid()
{	return 1;	}


void solve()
{

	int s=0,s1,b[17][17];
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if(st[i]==1)
				b[i][j]=-a[i][j];
			else
				b[i][j]=a[i][j];

	for(i=1;i<=m;i++)
		{
		s1=0;
		for(j=1;j<=n;j++)
			s1+=b[j][i];
		if(s1<0)
			s+=-s1;
		else
			s+=s1;
		}
	if(s>suma)
		suma=s;
}



void back()
{
	k=1;
	init();
	while(k>0)
	{
		as=1;ev=0;
		while(as&&!ev)
		{
			as=succ();
			if(as)	ev=valid();
		}
		if(as)
			if(sol())
				solve();
			else
			{
				k++;
				init();
			}
		else
			k--;
	}
}

int main()
{
	ifstream f("flip.in");
	ofstream g("flip.out");

	f>>n>>m;

	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			f>>a[i][j];


	back();
	g<<suma;
	return 0;
}