Cod sursa(job #1971215)

Utilizator TomaAlimosToma AlimoS TomaAlimos Data 19 aprilie 2017 23:25:58
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include<fstream>
using namespace std;

fstream fin("flip.in",ios::in),fout("flip.out",ios::out);

int n,m;
long a[17][17],S=0;

void read()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j];
}

struct candidate
{
    int pos;
    char LorC;

};

candidate c[33],pc[33];

void bild_candidate()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        c[i].pos=i;
        c[i].LorC='L';
    }
    for(j=n+1;j<=n+m;j++)
    {
        c[j].pos=j-n;
        c[j].LorC='C';
    }

}

void flip(candidate cand)
{
    int i,j;
    if(cand.LorC=='L')
        for(j=1;j<=m;j++)
            a[cand.pos][j]*=(-1);
    else
        for(i=1;i<=n;i++)
            a[i][cand.pos]*=(-1);
}


int sol(int k)
{
    //return (k==n+m ? 1 : 0);
    return 1;
}

int valid(int k)
{
    int i;
    for(i=1;i<=k-1;i++)
        if ((pc[i].pos==pc[k].pos)&&(pc[i].LorC==pc[k].LorC))
            return 0;
    return 1;
}

int sum()
{
    long s=0;
    int i, j;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            s+=a[i][j];
    return s;
}

void recalc(int k)
{
    long s=0;
    int i;
    for(i=1;i<=k;i++)
        flip(pc[i]);
    s=sum();
    if (s>S)
        S=s;
}

void backtrack(int k)
{
    for(int i=1;i<=n+m;i++)
    {
       pc[k].pos=c[i].pos;
       pc[k].LorC=c[i].LorC;
       if(valid(k))
       {
           recalc(k);
           backtrack(k+1);
       }
    }
}

void print()
{
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            fout<<a[i][j]<<' ';
        fout<<endl;
    }
}


int main()
{
    fin>>n>>m;
    read();
    //print();
    bild_candidate();
    /*for(int i=1;i<=n+m;i++)
        fout<<c[i].pos<<' '<<c[i].LorC<<' '<<endl;*/
    backtrack(1);
  //  print();
    fout<<S;//<<' '<<sum();
    return 0;
}