Cod sursa(job #685869)

Utilizator djgaby128Suciu Remus Gabriel djgaby128 Data 21 februarie 2012 11:27:34
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f;
ofstream g;
int n,k,st[20],i,j,v,m,S,s,maxim=0;
int a[16][16];
int x,y;
int sl(int a[16][16], int I) // sl - schimba linia || nl - numarul liniei || op . inmultire cu 1 sau -1 
{
	int J;
	for(J=1;J<=m;J++)
		a[I][J]=-a[I][J];
}
int vsuma(int a[16][16])
{
	 s=0; S=0;
	int I,J;
	for(I=1;I<=m;I++) 
	{ 
		for(J=1;J<=n;J++)
		{	s=s+a[I][J];
		}
		S=S+s;
	}
	
	return S;
}
void citire()
{
	f.open("flip.in");
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			f>>a[i][j];
}
// back
void init()
{
	k=1;
	st[k]=0;
}
void valid(int &v, int k)
{
	v=1; 
}
int succesor()
{
	if(st[k]<=x) return 1;
	return 0;
}
int solutie()
{
	if(k==x) return 1;
	return 0;
}
void tipar()
{	// S compari cu maxim 
	// 
	for(i=1;i<=x;i++)
	{
		if(st[i]==2)
		{
			sl(a,i);
 
			if(maxim<vsuma(a)) maxim=vsuma(a);
			sl(a,i); // undo - o face la loc
		}
	}
	
	 
}

void bkt()
{
	init();  
		while(k>0)
		{
		v=0;
		while( !v && st[k]<y)
			{
			st[k]++;
			valid(v,k);
			}
		if(!v)k--;
		else if(solutie()) tipar();
		else 
		{
        k++;
        st[k]=0;
        }
	} // de la while
}

int main()
{ 
	citire();
	x=n;
	y=2;
	bkt();
//	bkt(m,2);
	g.open("flip.out");
	g<<maxim;
}