Cod sursa(job #285021)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 22 martie 2009 11:45:19
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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;	} // tot timpu ii valid 


void solve()
{

	int s=0,s1,b[17][17];
	for(i=1;i<=n;i++)
	   if(st[i]==1)               
		  for(j=1;j<=m;j++)
			 b[i][j]=-a[i][j];   // defapt io o copiez in matricea b
	   else
	      for(j=1;j<=m;j++) 
	         b[i][j]=a[i][j]; 

	for(i=1;i<=m;i++)
		{
		s1=0; 
		for(j=1;j<=n;j++) // aici fac suma pe coloane
			s1+=b[j][i];  
		if(s1<0)      // daca ii < 0 inseamna ca o inmultesc cu -1
			s+=-s1;   // defapt io aduc la suma totala -s, adik --s care ii +s
		else
			s+=s1;
		}
	if(s>suma)    // daca ii > suma maxima retin maximul
		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();  //cand am ajuns la solutie, imi fac suma in matrice
			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;
}