Cod sursa(job #3201180)

Utilizator AnlegliftIvanus Victor Gabriel Anleglift Data 7 februarie 2024 00:25:31
Problema Jocul Flip Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>

using namespace std;

int N, M;
int matrix[50][50];

// Funcția pentru calcularea sumei
int calculateSum() {
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            sum += matrix[i][j];
        }
    }
    return sum;
}

// Funcția pentru aplicarea operației de flip pe o linie
void flipRow(int row) {
    for (int j = 0; j < M; ++j) {
        matrix[row][j] *= -1;
    }
}

// Funcția pentru aplicarea operației de flip pe o coloană
void flipCol(int col) {
    for (int i = 0; i < N; ++i) {
        matrix[i][col] *= -1;
    }
}

// Funcția recursivă pentru backtracking
int backtracking(int row) {
    // Dacă am terminat de parcurs toate liniile, calculăm suma și o returnăm
    if (row == N) {
        return calculateSum();
    }

    // Încercăm să aplicăm flip sau să trecem la următoarea linie
    int maxSum = 0;

    // Aplicăm flip pe linia curentă
    flipRow(row);
    maxSum = max(maxSum, backtracking(row + 1));
    flipRow(row); // Resetăm flip-ul

    // Trecem la următoarea linie
    maxSum = max(maxSum, backtracking(row + 1));

    return maxSum;
}

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

    fin >> N >> M;

    // Citim matricea de intrare
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            fin >> matrix[i][j];
        }
    }

    // Aplicăm backtracking-ul
    int result = backtracking(0);

    fout << result << endl;

    fin.close();
    fout.close();

    return 0;
}