Cod sursa(job #2079303)

Utilizator Marina23Oprea Marina Marina23 Data 30 noiembrie 2017 22:38:44
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>

using namespace std;

int i,j,N,M,A[20][20],Sum,Maxi,Sol[35];
bool B[20][20];

ifstream fin("flip.in");
ofstream fout("flip.out");

void backtrack(int Nivel)
{
    if(Nivel==N+M+1)
    {
        Sum=0;
        for(i=1;i<=N;i++)
            if(Sol[i]==1)
                for(j=1;j<=M;j++)
                    B[i][j]=1-B[i][j];
        for(i=N+1;i<=M+N;i++)
            if(Sol[i]==1)
                for(j=1;j<=N;j++)
                    B[j][i-N]=1-B[j][i-N];
        for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
            {
                if(B[i][j]==0)
                    Sum+=A[i][j];
                else
                    Sum-=A[i][j];
                B[i][j]=0;
            }
        if(Sum>Maxi)
            Maxi=Sum;
    }//if
    else
    {
        Sol[Nivel]=1;
        backtrack(Nivel+1);
        Sol[Nivel]=0;
        backtrack(Nivel+1);
    }//else
}

int main()
{

    fin>>N>>M;
    for(i=1;i<=N;i++)
        for(j=1;j<=M;j++)
            fin>>A[i][j];
    Maxi=-999999999;
    backtrack(1);
    fout<<Maxi;

    fin.close ();
    fout.close();
    return 0;
}