Cod sursa(job #1017396)

Utilizator Alina_MariaMateescu Adina Lenuta Maria Alina_Maria Data 27 octombrie 2013 19:03:21
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <iostream>
#include <stdio.h>

using namespace std;

// idee: se fixeaza coloanele sau liniile (una dintre) cu backtr. => toate posibilitatile
// pt fiecare posibilitate fixata, acum pot sa utilizez greedy si sa iau doar varianta cea mai buna pentru coloane.
// inainte nu puteam fiindca deciziile nu erau independente, se intrepatrundea linia cu coloana (un element comun)

int n, m, M[20][20], sScenariu1 = 0, sScenariu2 = 0, sMax = 0, aux, aux1;
int posibilitate[] = { -1, 1 };
int combinatii[50];

void citireFis() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            scanf("%d", &M[i][j]);
}

void calcSumaScenariu(int col) {
    sScenariu1 = 0;
    sScenariu2 = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; j++) {
            aux1 = M[i][j];
            if (j == col) {
                aux = aux1;
                sScenariu1 += (aux * combinatii[i] * (-1));
            }
            else {
                sScenariu1 += (aux1 * combinatii[i]);
            }
            sScenariu2 += (aux1 * combinatii[i]);
        }
    if (sScenariu1 > sMax)
        sMax = sScenariu1;
    if (sScenariu2 > sMax)
        sMax = sScenariu2;
}

void greedy() {
    for(int i = 0; i < m; ++i)
        calcSumaScenariu(i);
}

void backTracking(int k) {
    if(k == n) {
        greedy();
    } else {
        for(int i = 0; i < 2; ++i) {
            combinatii[k] = posibilitate[i];
            backTracking(k + 1);
        }
    }
}

int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);
    citireFis();
    backTracking(0);
    printf("%d", sMax);
    return 0;
}