Cod sursa(job #2197430)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 22 aprilie 2018 10:02:33
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int n, m, r, c;// se da o matrice de n pe m si trebuie sa elimin exact r linii si c coloane
int matr[101][101];//matricea contine numere naturale
int linie[101],coloana[101];
int operatieLinie[101], operatieColoana[101];
int sumMax;

void citire(){
    in >> n >> m >> r >> c;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            in >> matr[i][j];
        }
    }
}

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

void bktColoane(int varf){
    for(int i = coloana[varf - 1] + 1; i <= m; i++){
        coloana[varf] = i;
        operatieColoana[i] = 0;
        if(varf <= c){
            if(varf == c){
                int sumTemp = 0;
                for(int lin = 1; lin <= n; lin++){
                    if(operatieLinie[lin] != 0){
                        for(int col = 1; col <= m; col++){
                            sumTemp = sumTemp + matr[lin][col] * operatieColoana[col];
                        }
                    }
                }
                if(sumTemp > sumMax){
                    sumMax = sumTemp;
                }
            }else{
                bktColoane(varf + 1);
            }
        }
        operatieColoana[i] = 1;
    }
}

void bktLinii(int varf){
    for(int i = linie[varf - 1] + 1; i <= n; i++){
        linie[varf] = i;
        operatieLinie[i] = 0;
        if(varf <= r){
            if(varf == r){
                bktColoane(1);
            }else{
                bktLinii(varf + 1);
            }
        }
        operatieLinie[i] = 1;
    }
}

int main() {
    citire();
    initializareOperatii();
    bktLinii(1);
    out << sumMax;
    return 0;
}