Cod sursa(job #1978849)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 8 mai 2017 22:38:51
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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];

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

void coloane()
{
    int i;
    for(i=1; i<=m; i++)
        if(scol[i]<0)
            ss-=2*scol[i];
}

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;
            coloane();
            if(ss>s)
                s=ss;
            if(p<n)
                bk(p+1);
            flipl(i);
            l[i]=0;
        }
}

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;
    bk(1);
    fout<<s<<'\n';
    return 0;
}