Cod sursa(job #2443636)

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

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

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

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 si coloana are la sfarsit cate un element care memoreaza daca linia/coloana e flipped sau nu
    for(int i = 0; i < n; i++)
        a[i][m] = 1;
    for(int i = 0; i < m; i++)
        a[n][i] = 1;

}

///la fel functioneaza si functia sum
int sum(int lc) {
    int s = 0;
    if(lc < n)
        for(int i = 0; i < m; i++)
            s += a[lc][i];
    else
        for(int i = 0; i < n; i++)
            s +=a[i][lc-n];
    return s;
}

///functia flip schimba elementele de pe o linie (linia lc) daca lc < n(nr de lniii din matrice)
/// sau schimba elementele de pe coloana lc - n daca lc >= n
void flip(int lc) {
    currentS -= 2*sum(lc);
    if(lc < n) {
        for(int i = 0; i <= m; i++)
            a[lc][i] = -a[lc][i];
    } else {
        for(int i = 0; i <= n; i++)
            a[i][lc-n] = -a[i][lc-n];
    }
}

///folosind acelasi rationament ca in functia flip, functia isFlipped returneaza 1 daca linia lc/coloana lc-n este flipped sau -1 in caz contrar
int isFlipped(int lc) {
    if(lc < n)
        return a[lc][m];
    else
        return a[n][lc-n];
}

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;
}


void backtracking(int k) {
    for(int i = 0; i <= 1; i++) {
        if(isFlipped(k) != v[i]) {
            flip(k);
            //cout << "flip " << k << '\n';

            if(currentS > maxS) {
                maxS = currentS;
                //cout << maxS <<'\n';
            }
        }
        if(k < m+n-1)
            backtracking(k+1);
    }
}

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

    backtracking(0);

    g << maxS;
}