Cod sursa(job #2443643)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 28 iulie 2019 22:25:14
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream f("flip.in");
ofstream g("flip.out");

int n, m, a[17][17], maxS = -999999999, v[2] = {-1, 1};

void citire(int &n, int &m, int a[][17]) {
    f >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            f >> a[i][j];


    ///fiecare linie are la sfarsit cate un element care memoreaza daca linia e flipped sau nu
    for(int i = 0; i < n; i++)
        a[i][m] = 1;

}

///suma pe o coloana
int sum(int c) {
    int s = 0;
        for(int i = 0; i < n; i++)
            s +=a[i][c];
    return s;
}

///flip la linie
void flip(int l) {
        for(int i = 0; i <= m; i++)
            a[l][i] *= -1;
}

int Msum(int a[][17]) {
    int s = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            s+= a[i][j];
    return s;
}

///backtracking pt linii si pt a obtine suma maxima
///adunam abs de fiecare coloana
void backtracking(int k) {
    for(int i = 0; i <= 1; i++) {
        if(a[k][m] != v[i]) {
            flip(k);
            //cout << "flip " << k << '\n';
            int currentS = 0;
            for(int j = 0; j < m; j++)
                currentS+= abs(sum(j));
            if(currentS > maxS) {
                maxS = currentS;
                //cout << maxS <<'\n';
            }
        }
        if(k < n-1)
            backtracking(k+1);
    }
}

int main() {
    citire(n, m, a);
    maxS = Msum(a);

    backtracking(0);

    g << maxS;
}