Cod sursa(job #1660207)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 22 martie 2016 21:28:59
Problema Jocul Flip Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <utility>
#include <cstdlib>

#define NMAX 16

using namespace std;

int N, M; // dimensiunile tablei
int board[NMAX][NMAX]; // tabla de joc
int solution[NMAX]; // contine 1 sau -1 pe fiecare pozitie, adica cu cat sa se inmulteasca liniile
int maxSum = 0; // retine suma maxima obtinuta pentru fiecare configuratie

void read() {
    // dimensiunile matricei
    cin >> N >> M;

    // retine dimensiunea mai mica in N
    if (N > M) {
        swap(N, M);

        // elementele matricei
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                cin >> board[i][j];
            }
        }
    }
    else {
        // elementele matricei
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cin >> board[i][j];
            }
        }
    }
}

// calculeaza suma de pe tabla si o compara cu maximul curent
void computeSum() {
    int sum = 0;
    int lineSum;

    // calculeaza suma
    for (int i = 0; i < M; i++) {
        lineSum = 0;
        for (int j = 0; j < N; j++) {
            lineSum += board[i][j] * solution[j];
        }
        sum += abs(lineSum);
    }

    // actualizeaza suma maxima
    if (sum > maxSum) {
        maxSum = sum;
    }
}

// pe pozitia k adauga 1 sau -1
void backtrack(int k) {
    // daca a ajuns la sfarsitul backtracking-ului, programul face suma de pe tabla
    if (k >= N) {
        computeSum();
        return;
    }

    for (int i = 1; i >= -1; i -= 2) {
        solution[k] = i;
        backtrack(k + 1);
    }
}


int main() {
    freopen("flip.in", "r", stdin);
    freopen("flip.out", "w", stdout);

    read();
    backtrack(0);

    cout << maxSum;
}