Cod sursa(job #2197344)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 21 aprilie 2018 20:42:12
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int matr[17][17], n, m;
int sumMax;
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];
        }
    }
    in.close();
}

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){
    if(varf <= n + m){
        for(int oper = -1; oper <= 1; oper += 2){
            int temp1;
            sol[varf] = oper;
            if(varf <= n){
                temp1 = operatieLinie[varf];
                operatieLinie[varf] = oper;
            }else{
                temp1 = operatieCol[varf - n];
                operatieCol[varf - n] = oper;
            }
            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;
            }
                bkt(varf + 1);
            if(varf <= n){
                operatieLinie[varf] = temp1;
            }else{
                operatieCol[varf - n] = temp1;
            }
        }
    }
}

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