Pagini recente » Cod sursa (job #1448337) | Cod sursa (job #2631330) | Cod sursa (job #1816982) | Cod sursa (job #2284073) | Cod sursa (job #1660207)
#include <iostream>
#include <fstream>
#include <utility>
#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 = 0; // retine suma maxima obtinuta pentru fiecare configuratie
void read() {
// dimensiunile matricei
cin >> N >> M;
// retine dimensiunea mai mica in N
if (N > M) {
swap(N, M);
// elementele matricei
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
}
else {
// 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;
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);
}
// 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;
}