Cod sursa(job #24935)

Utilizator horia.jurcutHoria Jurcut horia.jurcut Data 4 martie 2007 00:56:45
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>

int st[100],n,m,a[17][17],b[17][17],smax,k,as,ev;

void citire()
{
 int i,j;

 FILE * in = fopen("flip.in","r");
 fscanf(in,"%d %d",&n,&m);
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
      fscanf(in,"%d",&a[i][j]);
 fclose(in);
}

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

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

int solutie()
{
 return 1;
}

void tipar()
{
 FILE * out = fopen("flip.out","w");
 fprintf(out,"%d",smax);
}

int validare()
{
int i,j,s0,stotal;
if(k>n) return 0;
for(i=1;i<k;i++)
 if(st[k]==st[i]) return 0;

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

for(i=1;i<=k;i++)
  {
   for(j=1;j<=m;j++)
      b[st[i]][j] *= (-1);
  }
stotal = 0;
for(i=1;i<=m;i++)
 {
 s0 = 0;
  for(j=1;j<=n;j++)
     {
      s0 += b[j][i];
     }
  if(s0<0) s0 *= (-1);
  stotal += s0;
 }
if(stotal>smax) smax = stotal;
return 1;
}


void bkt()
{
 k=1;
 init();
 while(k)
   {
    do
     {
      as=succesor();
      if(as) ev=validare();
     }while(as&&!ev);
    if(as)
      if(solutie());
      else
	{
	 ++k;
	 init();
	}
    else k--;
   }
}


int main()
{
citire();
bkt();
tipar();
return 0;
}