Cod sursa(job #2814983)

Utilizator raul41917raul rotar raul41917 Data 8 decembrie 2021 22:19:12
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#define MIN -256000001
using namespace std;
ifstream fi("flip.in");
ofstream fo("flip.out");
int n,m;
int M[17][17];
int VL[17],VC[17];
int putere(int exp)
{
    if(exp==1)
        return 1;
    else
        return -1;
}
int sumamatrice()
{
    int suma=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(VL[i]+VC[j]==0)
                suma+=(-M[i][j]);
            else
                suma+=M[i][j];
        }
    }
    return suma;
}
int maxim=MIN;
void backtracking2(int k)
{
    if(k<=n)
    {
        if(VL[k]==-1)
            {
                VC[k]=1;
                if(k<=m)
                    backtracking2(k+1);
                else
                {
                    int x=sumamatrice();
                        if(x>maxim)
                            maxim=x;
                }
            }else
            {
                for(int i=1;i<=2;i++)
                {
                    VC[k]=putere(i);
                    if(k<=m)
                    backtracking2(k+1);
                    else
                    {
                        int x=sumamatrice();
                        if(x>maxim)
                            maxim=x;
                    }
                }
            }
    }else
    {
        for(int i=1;i<=2;i++)
        {
            VC[k]=putere(i);
            if(k<=m)
                backtracking2(k+1);
            else
                {
                    int x=sumamatrice();
                    if(x>maxim)
                        maxim=x;
                }
        }
    }
}
void backtracking(int k)
{
    for(int i=1;i<=2;i++)
    {
        VL[k]=putere(i);
        if(k<=n)
            backtracking(k+1);
        else
        {
            backtracking2(1);
        }
    }
}
int main()
{
    fi>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            fi>>M[i][j];
    backtracking(1);
    fo<<maxim;
    return 0;
}