Cod sursa(job #613979)

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

int st[100],k,m,n;
long long int s,smax=0,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()
{
    if(k==n+m)
    {
        s=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(((st[i]==0)&&(st[n+j]==0))||((st[i]==1)&&(st[n+j]==1))) s+=a[i][j];
                    else s+=-a[i][j];
            }
    }
    return 1;
}
int solutie()
{
    return k==n+m;
}
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;
}