Cod sursa(job #3143220)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 28 iulie 2023 10:51:12
Problema Jocul Flip Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <climits>

using namespace std;

int n, m, a[20][20], sol = INT_MIN;
int subset[20], len;

void flip_line(int line) {
    for(int i = 1; i <= m; i++) {
        a[line][i] *= -1;
    }
}

void solve_subset() {
    for(int i = 1; i <= len; i++) {
        flip_line(subset[i]);
    }

    // undo:
    for(int i = 1; i <= len; i++) {
        flip_line(subset[i]);
    }
}

void backtrack(int nr) {
    // Am terminat de generat o submultime de linii:
    if(nr == n + 1) {
        solve_subset();
        return;
    }
    // Caz 1: nu il iau pe nr in submultimile pe care le generez next
    backtrack(nr + 1);

    // Caz 2: Il iau pe nr in submultimile pe care le generez next
    subset[++len] = nr;
    backtrack(nr + 1);
    --len; // undo
}

int main() {
    ifstream fin("flip.in");
    ofstream fout("flip.out");
    fin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            fin >> a[i][j];
        }
    }
    backtrack(1);
    return 0;
}