Cod sursa(job #24943)

Utilizator horia.jurcutHoria Jurcut horia.jurcut Data 4 martie 2007 01:21:28
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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]=-1;
}

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

int solutie()
{
 return (k==n);
}

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

int validare()
{
return 1;
}

int suma_max()
{
int i,j,s0,stotal;

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

for(i=1;i<=n;i++)
  {
  if(st[i]==1)
   for(j=1;j<=m;j++)
      b[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;
 }
return stotal;
}

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


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