Cod sursa(job #1978790)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 8 mai 2017 20:08:06
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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];
bool l[18], c[18];

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

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

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

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

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