Pagini recente » Cod sursa (job #1646997) | Cod sursa (job #238039) | Cod sursa (job #375321) | Cod sursa (job #1165716) | Cod sursa (job #1660261)
/**
* Solutie bazata pe backtracking. Intai se determina dimensiunea mai mica, se retine in N
* si se face backtracking de posibilitatile de flip-uire ale celor N linii. Dupa ce se ajunge
* la o solutie, programul face sumele pe cele M coloane, luand in considerare semnele din solutie.
* Daca una din sume este negativa, se inverseaza (adica se face flip pe acea coloana). La final,
* se afiseaza cea mai mare dintre sumele obtinute.
*/
#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; // retine suma maxima obtinuta pentru fiecare configuratie
bool firstTime = true; // folosit la initializarea sumei maxime
void read() {
// dimensiunile matricei
cin >> N >> M;
// retine dimensiunea mai mica in N
if (N > M) {
swap(N, M);
// citeste elementele matricei
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> board[j][i];
}
}
}
else {
// citeste 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++) {
// calculeaza suma pe linie, luand in considerare semnul generat de backtracking
lineSum = 0;
for (int j = 0; j < N; j++) {
lineSum += board[j][i] * solution[j];
}
// aduna suma pe linie in valoare absolute
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;
}