Cod sursa(job #1978845)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 8 mai 2017 22:28:53
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

int n, m;
int s, ss;
int a[18][18];
int scol[18];
bool l[18], c[18];

void flipl(int l)
{
    int i;
    for(i=1; i<=m; i++)
    {
        ss-=2*a[l][i];
        scol[i]-=2*a[l][i];
        if(scol[i]>0)
            c[i]=1;
        else
            c[i]=0;
        a[l][i]*=(-1);
    }
}

void flipc(int c)
{
    int i;
    for(i=1; i<=n; i++)
    {
        ss-=2*a[i][c];
        a[i][c]*=(-1);
    }
}


void bkc(int p)
{
    int i;
    for(i=1; i<=m; i++)
        if(!c[i])
        {
            c[i]=1;
            flipc(i);
            if(ss>s)
                s=ss;
            if(p<n)
                bkc(p+1);
            flipc(i);
            c[i]=0;
        }
}

void bk(int p)
{
    int i;
    for(i=1; i<=n; i++)
        if(!l[i])
        {
            l[i]=1;
            flipl(i);
            if(ss>s)
                s=ss;
            bkc(1);
            if(p<n)
                bk(p+1);
            flipl(i);
            l[i]=0;
        }
}

void calibreaza_coloane()
{
    int i;
    for(i=1; i<=m; i++)
        if(scol[i]>0)
            c[i]=1;
}

int main()
{
    fin>>n>>m;
    int i, j;
    for(i=1; i<=n; i++)
    {
        ss=0;
        for(j=1; j<=m; j++)
            fin>>a[i][j], ss+=a[i][j], scol[j]+=a[i][j];
        if(ss>0)
            l[i]=1;
        s+=ss;
    }
    ss=s;
    calibreaza_coloane();
    bk(1);
    fout<<s<<'\n';
    return 0;
}