Cod sursa(job #392091)

Utilizator CehashishChis Ovidiu Cehashish Data 6 februarie 2010 19:05:46
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<iostream.h>
#include<fstream.h>

int n,as,ev,m,b,k,k2,st[100],s=0,s1,d,a[100][100],c[100][100],st2[100];

void suma()
 {
	 for(int rer=1;rer<=n;rer++)
		 for(int rep=1;rep<=b;rep++)
			s1=s1+c[rer][rep];
}

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



void init2()
 {
	 if(k2==1) st2[k2]=0;
	  else st2[k2]=st2[k2-1];
}

int succesor()
 {
	 if(st[k]<n) {st[k]++;return 1;} 
 else return 0;
 }

int succesor2()
 {
	 if(st2[k2]<b) {st2[k2]++;return 1;} 
 else return 0;
 }

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

int valid2()
{ 
	for (int i=1;i<k2;i++)
if (st2[k2]==st2[i]) return 0;
return 1;
}

int solutie()
{
	return(k==m);
}
int solutie3()
{
	return(k2==d);
}

void tipar2()
{ s1=0;
  suma();
  
  if(s1>s) s=s1;
  s1=0;
  for(int t2=1;t2<=n;t2++)
		for(int y2=1;y2<=b;y2++)
		{int ok=1;
			for(int u2=1;u2<=d;u2++)
			 if(st2[u2]==y2) {s1=s1-c[t2][y2];ok=0;}
		  if(ok==1)	  s1=s1+c[t2][y2];
		}

if(s1>s) s=s1;
}

void bt3()
{
	 k2=1; init2();
	 while(k2>0)
	 { as=1;ev=0;
	   while (as && !ev)
	   { as=succesor2();
	     if(as) ev=valid2();
	   }
	   
	   if(as!=0)
	   if (solutie3()) tipar2();
	    else{k2++;init2(); }
		else k2--;
	   } 
	 }

void tipar()
 { for(int t=1;t<=n;t++)
		for(int y=1;y<=b;y++)
			c[t][y]=a[t][y];
	
	for(int t=1;t<=n;t++)
		for(int y=1;y<=b;y++)
			for(int u=1;u<=m;u++)
			  if(st[u]==t) c[t][y]=-c[t][y];
	
	for (d=1;d<=b;d++)		
		bt3();		 

 }

void bt()
 {
	 k=1; init();
	 while(k>0)
	 { as=1;ev=0;
	   while (as && !ev)
	   { as=succesor();
	     if(as) ev=valid();
	   }
	   
	   if(as!=0)
	   if (solutie()) tipar();
	    else{k++;init(); }
		else k--;
	   } 
	 }
	 
int main()
 {
	 ifstream f;f.open("flip.in");
		 ofstream g;g.open("flip.out");
	 f>>n>>b;	 
	 for(int i=1;i<=n;i++)
		 for(int j=1;j<=b;j++)
			 {
				 f>>a[i][j];
				 s=s+a[i][j];
		 }
	 
	for(m=0;m<=n;m++)
	  bt();
	 cout<<s;
	 f.close();
	 g.close();
	 return 0;
}