Cod sursa(job #102392)

Utilizator the_alch3m1stJeler Stefan the_alch3m1st Data 14 noiembrie 2007 12:54:52
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<iostream.h>
#include<fstream.h>

typedef int stiva[100];
int n,k,ev,as,a[1<<4][1<<4],N,M,b[1<<4][1<<4],c[1<<4][1<<4];
int suma=0;
stiva st;
void citire()
{int i,j;
     fstream fin("flip.in",ios::in);
     fin>>N;
     fin>>M;
     for(i=1;i<=N;i++)
     for(j=1;j<=M;j++) fin>>a[i][j];
     fin.close();
     
 }

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

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

int valid()
{
    return 1;
}

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

{
    int i,j,suma=0;
    for(i=1;i<=N;i++)
    for(j=1;j<=M;j++)
    suma+=b[i][j];
return suma;
}

void reset()
{
    int i,j;
    for(i=1;i<=N;i++)
    for(j=1;j<=M;j++)
    b[i][j]=a[i][j];
}
     
void flip()
{    int i,j,s;
     reset();
     for(i=1;i<=N;i++)
                      for(j=1;j<=M;j++)if(st[j]==1) b[i][j]*=-1;
                      
     for(i=1;i<=N;i++)
     {s=0;
     for(j=1;j<=M;j++)s+=b[i][j];
     if (s<0)
        { for(j=1;j<=M;j++)b[i][j]*=-1;
        }
        
     }
     s=suma_b();
     if(s>suma) suma=s;
     
                      
     
}

void bt()
{
     k=1;
     init();
     while(k>0)
     {
               as=1;ev=0;
               while(as && !ev)
               {
                        as=succesor();
                        if(as) ev=valid();
               }
     if(as)
           if(solutie())flip();
                                else {k++;init();}
           else k--;
           
     }
}


void scrie()
{
     fstream fout("flip.out",ios::out);
     fout<<suma;
     fout.close();
}
int main()
{
 citire();
 n=M;
 bt();
 scrie();

}