Cod sursa(job #939971)

Utilizator alecsandrualex cuturela alecsandru Data 15 aprilie 2013 11:25:04
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<cstdio>
using namespace std;
int smin,i,j,n,m,v[20][20],ind,tip,smat,slin[20],scol[20];
void search()
{
    int s;
    smin=2000000000;
    for(i=1;i<=n;i++)
    {
        if(slin[i]<smin)
        {
            smin=slin[i];
            ind=i;
            tip=1;
        }
    }
    for(i=1;i<=m;i++)
    {
        if(scol[i]<smin)
        {
            smin=scol[i];
            ind=i;
            tip=2;
        }
    }
}
bool valid()
{
    int stemp;
    if(tip==1)
        stemp=smat-slin[ind]-smin;
    else
        stemp=smat-scol[ind]-smin;
    if(stemp>smat)
    {
        smat=stemp;
        if(tip==1)
            slin[ind]=-smin;
        else
            scol[ind]=-smin;
        return 1;
    }
    else
        return 0;

}
int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%d",&v[i][j]);
            smat+=v[i][j];
            slin[i]+=v[i][j];
        }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
        {
            scol[i]+=v[j][i];
        }
    while(1)
    {
        search();
        if(valid())
            continue;
        else
            break;
    }
    printf("%d",smat);
    return 0;
}