Cod sursa(job #913525)

Utilizator mick4224Mihai Daniel mick4224 Data 13 martie 2013 16:46:20
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int a[17][17],N,M,lp[17],ln[17],cn[17],cp[17];
int linsch()//care linie ar putea fi schimbata
{
    int l=0,i;
    int dl=0;
    for(i=1;i<=N;i++)
        if((-1)*ln[i]>lp[i] && (-ln[i]-lp[i])>dl)
        {
            l=i;
            dl=-ln[i]-lp[i];
        }
    //cout<<"#"<<dl<<"#";
    return l;
}
int colsch()//care coloana ar putea fi schimbata
{
    int l=0,i;
    int dl=0;
    for(i=1;i<=M;i++)
        if((-1)*cn[i]>cp[i] && (-1)*cn[i]-cp[i]>dl)
        {
            l=i;
            dl=(-1)*cn[i]-cp[i];
        }
    return l;
}
void schlin(int i)
{
    int j;
    for(j=1;j<=M;j++)
        a[i][j]=a[i][j]*(-1);
}
void schcol(int i)
{
    int j;
    for(j=1;j<=N;j++)
        a[j][i]=a[j][i]*(-1);
}

int main()
{
    int i,j,l,c,ok,aux;

    f>>N>>M;
    for(i=1;i<=N;i++)
        for(j=1;j<=M;j++)
        {
            f>>a[i][j];
            if(a[i][j]>0)
            {
                lp[i]+=a[i][j];
                cp[j]+=a[i][j];
            }
            else
            {
                ln[i]+=a[i][j];
                cn[j]+=a[i][j];
            }
        }

    do
    {
        ok=1;
        l=colsch();
        if(l>0)
        {
            ok=0;
            schcol(l);
            aux=cn[l];
            cn[l]=cp[l];
            cp[l]=aux;
            cn[l]=-cn[l];
            cp[l]=-cp[l];
            for(j=1;j<=N;j++)
                if(a[j][l])
                {
                    ln[j]+=a[j][l];
                    lp[j]+=a[j][l];
                }
                else
                {
                    ln[j]-=a[j][l];
                    lp[j]-=a[j][l];
                }
        }
        l=linsch();
        if(l>0)
        {
            ok=0;
            schlin(l);
            aux=ln[l];
            ln[l]=lp[l];
            lp[l]=aux;
            ln[l]=-ln[l];
            lp[l]=-lp[l];
            for(j=1;j<=M;j++)
                if(a[l][j])
                {
                    cn[j]+=a[l][j];
                    cp[j]+=a[l][j];
                }
                else
                {
                    cn[j]-=a[l][j];
                    cp[j]-=a[l][j];
                }
        }

    }
    while(!ok);
    /*for(i=1;i<=N;i++)
    {
        for(j=1;j<=M;j++)
            g<<a[i][j]<<" ";
        g<<"\n";
    }*/
    int s=0;
    for(i=1;i<=N;i++)
        s+=(lp[i]+ln[i]);
    g<<s<<"\n";
    g.close();
    f.close();
    g.close();
    return 0;
}