Cod sursa(job #2832786)

Utilizator daniel23Malanca Daniel daniel23 Data 14 ianuarie 2022 12:08:50
Problema Jocul Flip Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>

int n, m;
int arr[16][16];
int max;
int count = 0;

std::ifstream in("flip.in");
std::ofstream out("flip.out");

bool com[2][16];
int schimbat[32];
int l_abs = 0;

int s_linii[16];
int s_coloane[16];

void solve(int sum) {
    if (sum > max) max = sum;
    int l = 0;

    for (int i=0; i<n; i++) {
        if (com[0][i]) continue;

        if (s_linii[i] < 0) {
            s_linii[i] *= -1;
            for (int j=0; j<m; j++)
                s_coloane[j] -= 2*arr[i][j];   
            com[0][i] = 1;
            schimbat[(l++, l_abs++)] = i;
            solve(sum + 2*s_linii[i]);
            s_linii[i] *= -1;
            for (int j=0; j<m; j++)
                s_coloane[j] += 2*arr[i][j];   
        }
    }

    for (int i=0; i<m; i++) {
        if (com[1][i]) continue;

        if (s_coloane[i] < 0) {
            for (int j=0; j<n; j++)
                s_linii[j] += -2*arr[j][i];
            s_coloane[i] *= -1;
            com[1][i] = 1;
            schimbat[(l++, l_abs++)] = 16 + i;
            solve(sum + 2*s_coloane[i]);
            s_coloane[i] *= -1;
            for (int j=0; j<n; j++)
                s_linii[j] += 2*arr[j][i];
        }
    }

    for (int i=0; i<l; i++) {
        (*(com[0] + schimbat[--l_abs])) = 0;
    }
}

int main() {
    in >> n >> m;

    int sum = 0;

    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
            in >> arr[i][j],
            sum += arr[i][j],
            s_linii[i] += arr[i][j],
            s_coloane[j] += arr[i][j];

    max = sum;
    solve(sum);

    out << max;
}