Cod sursa(job #879418)

Utilizator aleph0Ionut-Gabriel Radu aleph0 Data 15 februarie 2013 13:26:01
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <climits>
#include <iostream>
#include <fstream>

#define MAX_DIM 16

void find_solution(const int* options,
                   int arr[MAX_DIM][MAX_DIM],
                   const int m,
                   const int n,
                   int& solution)
{
    int total_sum = 0;
    for (int i = 0; i < m; i++) {
        int sum_line = 0;
        for (int j = 0; j < n; j++) {
            if (options[j] == -1) {
                sum_line -= arr[i][j];
            } else {
                sum_line += arr[i][j];
            }
        }
        if (sum_line < 0) {
            total_sum -= sum_line;
        } else {
            total_sum += sum_line;
        }
    }
    if (solution < total_sum) {
        solution = total_sum;
    }
}

void backtrack(int k,
               int* options,
               int arr[MAX_DIM][MAX_DIM],
               const int m,
               const int n,
               int& solution)
{
    int flip_flop[] = {-1, 1};
    if (k == n) {
        find_solution(options, arr, m, n, solution);
        return;
    }

    for (int i = 0; i < 2; i++) {
        options[k] = flip_flop[i];
        backtrack(k + 1, options, arr, m, n, solution);
    }
}

int main(int argc, char** argv)
{
    std::ifstream in("flip.in");
    std::ofstream out("flip.out");
    int arr[MAX_DIM][MAX_DIM];
    int options[MAX_DIM];
    int m, n, solution;

    // Read the matrix dimension
    in >> m >> n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            in >> arr[i][j];
        }
    }

    // Find the maximum possible sum
    solution = INT_MIN;
    backtrack(0, options, arr, m, n, solution);

    out << solution;
    in.close();
    out.close();
    return 0;
}