Cod sursa(job #759587)

Utilizator andrei.stoicaStoica Andrei andrei.stoica Data 18 iunie 2012 18:21:22
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<cstdlib>

using namespace std;

int N,M;
int a[16][16];

void iesire ()
{
  //iese explicit din bkt
}

void fliplin (int i)
{
  for (int k=0 ; k<M ; ++k)
  { 
    *(a[i]+k)*=(-1);
  }
}

void flipcol (int i)
{
  for (int k=0 ; k<N ; ++k)
  {
    *(a[k]+i)*=(-1); 
  }
}

void bktlin (int *sum)
{
  static int i=0;
  if (i==N)
  {
    iesire();
  }
  else
  {
    int sum1=0,sum2=0,aux;
    for (int j=0 ; j<M ; ++j)
    { 
      aux=*(a[i]+j);
      sum1+=aux;
      sum2+=aux*(-1);
    }
    if (sum1<sum2)
    {
      *sum=*sum-sum1+sum2;
      fliplin(i);
    }
    ++i;
    bktlin(sum);
  }
}

void bktcol (int *sum) 
{
  static int i=0;
  if (i==M)
  {
    iesire();
  }
  else
  {
    int sum1=0,sum2=0,aux;
    for (int j=0 ; j<N ; ++j)
    {
      aux=*(a[j]+i);
      sum1+=aux;
      sum2+=aux*(-1);
    }
    if (sum1<sum2)
    {
      *sum=*sum-sum1+sum2;
      flipcol(i);
    }
    ++i;
    bktcol(sum);
  }
}

int main ()
{
  int sum=0,aux=-1000000;
  FILE *in, *out;
  in=fopen("flip.in","r");
  if (in==NULL)
  {
    exit(1);
  }
  out=fopen("flip.out","w");
  if (out==NULL)
  {
    exit(2);
  }
  fscanf(in,"%d%d",&N,&M);
  for (int i=0 ; i<N ; ++i)
  {
    for (int j=0 ; j<M ; ++j)
    {
      fscanf(in,"%d",&a[i][j]);
      sum+=a[i][j];
    }
  }
  aux=sum;
  while (1)
  {
    bktcol(&sum);
    aux=sum;
    bktlin(&aux);
    if (aux>sum)
      sum=aux;
    else
      break;
  }
  fprintf(out,"%d\n",sum);
  fclose(in);
  fclose(out);
  return 0;
}