Cod sursa(job #613981)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 5 octombrie 2011 11:18:01
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
using namespace std;

int st[100],k,m,n;
long long int s,smax=0,ss,a[17][17];
ofstream g ("flip.out");

void init()
{
    st[k]=-1;
}
int am_succesor()
{
    if(st[k]<1)
    {
        st[k]++;
        return 1;
    }
    return 0;
}
int e_valid()
{
    s=0;
    if(k==n)
    {
        for(int i=1;i<=m;i++)
        {
            ss=0;
            for(int j=1;j<=n;j++)
            {
                if(st[j]==0) ss+=a[j][i];
                    else ss+=-a[j][i];
            }
            if(ss>0) s+=ss;
                else s+=-ss;
        }
    }
    return 1;
}
int solutie()
{
    return k==n;
}
void afis()
{
    if(s>smax) smax=s;
}
void back()
{
    int as; k=1; init();
    while(k>0)
    {
        do{} while((as=am_succesor())&&(!e_valid()));
        if(as)
        {
            if(solutie()) afis();
            else {k++; init();}
        }
        else k--;
    }
}
int main()
{
    ifstream f ("flip.in");
    f>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) f>>a[i][j];
    back();
    g<<smax;
}