Pagini recente » Cod sursa (job #2744555) | Cod sursa (job #2744923) | Cod sursa (job #2450340) | Cod sursa (job #1840652) | Cod sursa (job #2197339)
#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;
}