Cod sursa(job #2976731)

Utilizator Tudor_MateiHolota Tudor Matei Tudor_Matei Data 9 februarie 2023 22:05:23
Problema Jocul Flip Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
using namespace std;
ifstream cin("flip.in");
ofstream cout("flip.out");
const int N = 20;
int n, m;
int a[N][N];
int ans;

void dfs(int step, int sum) {
    // Daca am parcurs toate liniile si coloanele, actualizez valoarea maxima a sumei
    if (step == n + m) {
        ans = max(ans, sum);
        return;
    }

    // Aleg sa las linia sau coloana asa cum este
    dfs(step + 1, sum);

    // Inversez linia sau coloana (in functie de pasul actual)
    int x = step, y = 0;
    if (x >= n) {
        x = n - 1;
        y = step - n + 1;
    }
    int tmp = 0;
    for (int i = 0; i < n; i++) {
        a[i][y] *= -1;
        tmp += a[i][y];
    }
    for (int j = 0; j < m; j++) {
        a[x][j] *= -1;
        tmp += a[x][j];
    }
    // Apelez recursiv functia si adaug suma elementelor liniei sau coloanei
    dfs(step + 1, sum + tmp);

    // Inversez inapoi linia sau coloana
    for (int i = 0; i < n; i++) {
        a[i][y] *= -1;
    }
    for (int j = 0; j < m; j++) {
        a[x][j] *= -1;
    }
}

int main() {
    // Citirea datelor de intrare
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    // Apelarea functiei de cautare
    dfs(0, 0);

    // Afisarea rezultatului
    cout << ans << endl;
    return 0;
}