Cod sursa(job #3003594)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 15 martie 2023 20:07:13
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
/*
Generam toate posibilitatile de flip pentru coloane:
1. Ele sunt siruri de 0 si 1 de lungime m
2. Ele sunt submultimi ale {1, 2, 3, ..., m}

Backtracking => metoda recursiva de a genera lucruri
// 1. Decizii: Pentru fiecare coloana de la 1 la m, o flipuim sau nu?
*/
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

vector<int> coloane;
int n, m, a[20][20], sol = -INT_MAX;

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

void flip_col(int col) {
    for(int lin = 1; lin <= n; lin++) {
        a[lin][col] *= -1;
    }
}

void backtracking(int col) {
    // Punct de oprire:
    if(col == m + 1) {
        // In coloane am subsetul curent generat
        // Mai intai flipuiesc coloanele:
        for(int col : coloane) {
            flip_col(col);
        }
        int total = 0;
        for(int lin = 1; lin <= n; lin++) {
            int sum = 0;
            for(int j = 1; j <= m; j++) {
                sum += a[lin][j];
            }
            total += abs(sum);
        }
        sol = max(sol, total);
        // Undo:
        for(int col : coloane) {
            flip_col(col);
        }
        return;
    }
    //Luam decizia pentru col:
    // Decizia 1: nu o adaugam in subset
    backtracking(col + 1); // genereaza toate solutiile fara col in subset
    // Decizia 2: o adaugam in subset
    coloane.push_back(col);
    backtracking(col + 1); // genereaza toate solutiile cu col in subset
    coloane.pop_back();
}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            fin >> a[i][j];
        }
    }
    backtracking(1);
    fout << sol << "\n";
    return 0;
}