Pagini recente » Cod sursa (job #3229193) | Cod sursa (job #976815) | Cod sursa (job #2151662) | Cod sursa (job #3254197) | Cod sursa (job #1660225)
#include <iostream>
#include <fstream>
#include <cstdlib>
#define NMAX 16
using namespace std;
int N, M; // dimensiunile tablei
int board[NMAX][NMAX]; // tabla de joc
int solution[NMAX]; // contine 1 sau -1 pe fiecare pozitie, adica cu cat sa se inmulteasca liniile
int maxSum; // retine suma maxima obtinuta pentru fiecare configuratie
bool firstTime = true; // folosit la initializarea sumei maxime
void read() {
// citeste dimensiunile matricei
cin >> N >> M;
// citeste elementele matricei
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
}
// calculeaza suma de pe tabla si o compara cu maximul curent
void computeSum() {
int sum = 0;
int lineSum;
// calculeaza suma
for (int i = 0; i < M; i++) {
lineSum = 0;
for (int j = 0; j < N; j++) {
lineSum += board[i][j] * solution[j];
}
sum += abs(lineSum);
}
if (firstTime == true) {
firstTime = false;
maxSum = sum;
}
// actualizeaza suma maxima
if (sum > maxSum) {
maxSum = sum;
}
}
// pe pozitia k adauga 1 sau -1
void backtrack(int k) {
// daca a ajuns la sfarsitul backtracking-ului, programul face suma de pe tabla
if (k >= N) {
computeSum();
return;
}
for (int i = 1; i >= -1; i -= 2) {
solution[k] = i;
backtrack(k + 1);
}
}
int main() {
freopen("flip.in", "r", stdin);
freopen("flip.out", "w", stdout);
read();
backtrack(0);
cout << maxSum;
}