Cod sursa(job #1856356)

Utilizator AurelGabrielAurel Gabriel AurelGabriel Data 24 ianuarie 2017 19:47:47
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>

using namespace std;

int n, m;
long int a[16][16];

long int mx = -16000000;

int l[16];
int c[16];

bool vf(int* v, unsigned int sz)
{
    for(unsigned int i = 0; i < sz; i++)
        if(v[i] == v[sz])
            return false;
    return true;
}

long int calcSum()
{
    long int s = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            s+=a[i][j];
    return s;
}

void flipl(int l)
{
    for(int i = 0; i < m; i++)
        a[l][i] = -a[l][i];
}

void flipc(int c)
{
    for(int i = 0; i < n; i++)
        a[i][c] = -a[i][c];
}

void backtrack(int k)
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            if(k < n)
                l[k] = i;
            if(k < m)
                c[k] = j;

            if(vf(l, k) && vf(l, k))
            {
                flipl(j);
                flipc(i);

                mx = max(mx, calcSum());

                backtrack(k+1);
            }
        }

}

int main()
{
    ifstream f("flip.in");
    ofstream g("flip.out");

    f >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        f >> a[i][j];

    backtrack(0);


    g << mx;


    return 0;
}