Pagini recente » Cod sursa (job #2014654) | Cod sursa (job #338514) | Cod sursa (job #1724768) | Cod sursa (job #1008566) | Cod sursa (job #1660180)
#include <iostream>
#include <fstream>
#define NMAX 16
using namespace std;
int N, M; // dimensiunile tablei
int board[NMAX][NMAX]; // tabla de joc
int solution[2 * NMAX]; // contine 1 sau -1 pe fiecare pozitie, adica cu cat sa se inmulteasca liniile si coloanele
int maxSum = 0; // retine suma maxima obtinuta pentru fiecare configuratie
void read() {
// dimensiunile matricei
cin >> N >> M;
// elementele matricei
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
}
}
}
// calculeaza suma de pe tabla si o compara cu maximul curent
void computeSum() {
int sum = 0;
// calculeaza suma
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sum += board[i][j] * solution[i] * solution[N + j];
}
}
// 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 + M) {
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;
}