Cod sursa(job #2814981)

Utilizator raul41917raul rotar raul41917 Data 8 decembrie 2021 22:05:14
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 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)
{
    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;
}