Cod sursa(job #972351)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 11 iulie 2013 14:56:14
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
using namespace std;
ifstream f("flip.in");
ofstream g("flip.out");
int Matrix[17][17],Line_sum[17],Col_sum[17],x[17],maximum=-32000001,y[17];
int sum;
int N,M;
void Read()
{
    int i,j;
    f>>N>>M;
    for(i=1;i<=N;i++)
        for(j=1;j<=M;j++)
        {
            f>>Matrix[i][j];
            Line_sum[i]+=Matrix[i][j];
            Col_sum[j]+=Matrix[i][j];
            sum+=Matrix[i][j];
        }
    sum*=2;
    if(sum/2>maximum)
        maximum=sum/2;
}
void Count()
{
    int i,j;
    sum=0;
    for(i=1;i<=N;i++)
        for(j=1;j<=M;j++)
            sum+=Matrix[i][j];
    if(maximum<sum)
        maximum=sum;
}
void backcol(int k)
{
    int i,j;
    for(i=y[k-1]+1;i<=M;i++)
    {
        y[k]=i;
        for(j=1;j<=N;j++)
            Matrix[j][i]*=-1;
        Count();
        if(k<M)
        {
            backcol(k+1);
            for(j=1;j<=N;j++)
                Matrix[j][i]*=-1;
        }
    }
   for(j=1;j<=N;j++)
        Matrix[j][i-1]*=-1;
}
void backline(int k)
{
    int i,j;
    for(i=x[k-1]+1;i<=N;i++)
    {
        x[k]=i;
        for(j=1;j<=M;j++)
            Matrix[i][j]*=-1;
        Count();
        backcol(1);
        if(k<N)
        {
            backline(k+1);
            for(j=1;j<=M;j++)
                Matrix[i][j]*=-1;
        }
    }
    for(j=1;j<=M;j++)
        Matrix[i-1][j]*=-1;
}
int main()
{
    Read();
    backline(1);
    g<<maximum<<"\n";
    return 0;
}