Cod sursa(job #2145707)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 27 februarie 2018 16:03:32
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#define DMAX 20

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

int m, n;
int mat[DMAX][DMAX];

int sol;
int invLin[DMAX];
int invCol[DMAX];

void bktCol(int pos) {
    if (pos == n + 1) {
        int sum = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                sum += mat[i][j] * invLin[i] * invCol[j];

        if (sum > sol)
            sol = sum;
        return;
    }

    invCol[pos] *= -1;
    bktCol(pos + 1);

    invCol[pos] *= -1;
    bktCol(pos + 1);
}

void bktLin(int pos) {
    if (pos == m + 1) {
        bktCol(1);
        return;
    }

    invLin[pos] *= -1;
    bktLin(pos + 1);

    invLin[pos] *= -1;
    bktLin(pos + 1);
}

int main() {
    fin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            fin >> mat[i][j];
            invLin[i] = invCol[j] = +1;
        }

    bktLin(1);
    fout << sol << '\n';

    fout.close();
    return 0;
}