Cod sursa(job #2078741)

Utilizator AndaionicaIonica Anda Maria Andaionica Data 29 noiembrie 2017 21:26:42
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int i,j,q1[17],q2[17],s,Max,v[17][17],n,m,s1[17],s2[17];
void back(int x,int y)
{
    int i,j,k;
    for(j=y+1;j<=m;j++)
    {
        q1[x]*=(-1);
        q2[j]*=(-1);
        int t=s;
        s-=(s1[x]+s2[j]-v[x][j]);
        for(k=1;k<=n;k++)
            s+=v[k][j]*q1[k]*q2[j];
        for(k=1;k<=m;k++)
            s+=v[x][k]*q1[x]*q2[k];
        s-=v[x][j]*q1[x]*q2[j];
        Max=max(Max,s);
        if(x<=n&&y<m)
            back(x,j+1);
            else
                if(x<n&&y==m)
                    back(x+1,1);
        s=t;
        q2[j]*=(-1);
        q1[x]*=(-1);
    }
    for(i=x+1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            q1[i]*=(-1);
            q2[j]*=(-1);
            int t=s;
            s-=(s1[i]+s2[j]-v[i][j]);
            for(k=1;k<=n;k++)
                s+=v[k][j]*q1[k]*q2[j];
            for(k=1;k<=m;k++)
                s+=v[i][k]*q1[i]*q2[k];
            s-=v[i][j]*q1[i]*q2[j];
            Max=max(Max,s);
            if(x<=n&&y<m)
                back(i,j+1);
                else
                    if(x<n&&y==m)
                        back(i+1,1);
            s=t;
            q2[j]*=(-1);
            q1[i]*=(-1);
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        q1[i]=1;
        for(j=1;j<=m;j++)
        {
            f>>v[i][j];
            s+=v[i][j];
            s1[i]+=v[i][j];
            s2[j]+=v[i][j];
        }
    }
    for(j=1;j<=m;j++)
        q2[j]=1;
    Max=s;
    back(1,1);
    g<<Max;
    return 0;
}