Cod sursa(job #1311427)

Utilizator vladttturcuman vlad vladtt Data 8 ianuarie 2015 09:51:10
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

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

int n,i,j,m,s,maxx;
int l[20],c[20];
int qw[20][20];

int recalc_l(int lin)
{
    int part=0;
    for(int i=1;i<=m;i++)
    {
        part+=qw[lin][i]*l[lin]*c[i];
    }
    part=part*2;
    return part;
}

int recalc_c(int lin)
{
    int part=0;
    for(int i=1;i<=n;i++)
    {
        part+=qw[i][lin]*l[i]*c[lin];
    }
    part=part*2;
    return part;
}

int backtrack(int k)
{
    int part=0;
    if(k==5)
        return 0;
    for(int i=1;i<=n;i++)
    {
        l[i]=l[i]*(-1);
        part=recalc_l(i);
        s+=part;
        if(maxx<s)
            maxx=s;
        backtrack(k+1);
        l[i]=l[i]*(-1);
        s-=part;
    }
    for(int i=1;i<=m;i++)
    {
        c[i]=c[i]*(-1);
        part=recalc_c(i);
        s+=part;
        if(maxx<s)
            maxx=s;
        backtrack(k+1);
        c[i]=c[i]*(-1);
        s-=part;
    }
    return 0;
}

int main()
{
    for(i=1;i<=20;i++)
        l[i]=c[i]=1;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            fin>>qw[i][j];
            s+=qw[i][j];
        }
    backtrack(1);
    fout<<maxx;
    return 0;
}