Cod sursa(job #429043)

Utilizator palcuiealexAlex Palcuie palcuiealex Data 29 martie 2010 19:51:45
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;

int v[17][17],n,m,sl[2][17],sc[2][17],s,smax,nn,mm;
// TODO (Alex#1#): bitset
bool l[19],c[19];
void afis()
{
    int i,j;
    for (i=1;i<=n;++i)
    {
    for (j=1;j<=m;++j) cout<<v[i][j]<<' '; cout<<'\n';
    } cout<<'\n';
    return;
}
void schimba(int k,bool b)
{
    int i;
    if (b) //linie
    {
        for (i=1;i<=n;++i)
        {
            v[k][i]=-v[k][i];
            //sl[1][k]+=v[k][i];
            //sc[0][i]+=v[k][i];
            s+=v[k][i];
            if (s>smax) smax=s;
        }
    }
    else //coloana
    {
        for (i=1;i<=n;++i)
        {
            v[i][k]=-v[i][k];
            //sl[1][i]+=v[i][k];
            //sc[0][k]+=v[i][k];
            s+=v[i][k];
            if (s>smax) smax=s;
        }
    }
}


void back(int k,bool b)
{
    if (b) //linie
    {
        if (k==nn) return;
        if (!l[k])
        {
            back(1,0);
            l[k]=1;
            schimba(k,1);
            back(1,0);
            back(k+1,1);
            l[k]=0;
            schimba(k,1);
            back(k+1,1);
        }
        else back(k+1,1);
        return;
    }
    else  //coloana
    {
        if (k==mm) return;
        if (!c[k])
        {
            back(k+1,0);
            c[k]=1;
            schimba(k,0);
            back(k+1,0);
            schimba(k,0);
            c[k]=0;
            back(k+1,0);
        }
        else back(k+1,0);
        return;
    }
}

int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    int i,j;
    cin>>n>>m; nn=n+1;mm=m+1;
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
        {
            cin>>v[i][j];
            s+=v[i][j];
            sl[v[i][j]>0][i]+=v[i][j];
            sc[v[i][j]>0][j]+=v[i][j];
        }

    smax=s;
    back(1,1);
    printf("%d",smax);
    return 0;
}