Cod sursa(job #2197339)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 21 aprilie 2018 20:01:26
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int matr[17][17], n, m;
int sumLin[17], sumCol[17];
int sumMax, elemNegative[36],nrElem;
int sol[50];
int operatieLinie[17], operatieCol[17];

void citire(){
    in >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            in >> matr[i][j];
            sumMax = sumMax + matr[i][j];
            sumLin[i] = sumLin[i] + matr[i][j];
            sumCol[j] = sumCol[j] + matr[i][j];
        }
    }
    in.close();
}

void selectieNegative(){
    for(int i = 1; i <= n; i++){
        if(sumLin[i] < 0){
            elemNegative[++nrElem] = i;
        }
    }
    for(int i = 1; i <= m; i++){
        if(sumCol[i] < 0){
            elemNegative[++nrElem] = i + n;//numerotez coloanele de la n+1 incolo
        }
    }
}

void initializareOperatie(){
    for(int i = 1; i <= n; i++){
        operatieLinie[i] = 1;
    }
    for(int j = 1; j <= m; j++){
        operatieCol[j] = 1;
    }
}

void bkt(int varf){
    for(int i = sol[varf - 1] + 1; i <= nrElem; i++){
        sol[varf] = i;
        if(elemNegative[i] <= n){
            operatieLinie[elemNegative[i]] = -1;
        }else{
            operatieCol[elemNegative[i] - n] = -1;
        }
        int sumaTemp = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                sumaTemp = sumaTemp + matr[i][j]*operatieLinie[i]*operatieCol[j];
            }
        }
        if(sumaTemp > sumMax){
            sumMax = sumaTemp;
        }
        if(varf < nrElem){
            bkt(varf + 1);
        }
        if(elemNegative[i] <= n){
            operatieLinie[elemNegative[i]] = 1;
        }else{
            operatieCol[elemNegative[i] - n] = 1;
        }
    }
}

int main() {
    citire();
    selectieNegative();
    initializareOperatie();
    bkt(1);
    out << sumMax;
    return 0;
}