Pagini recente » Cod sursa (job #2718528) | Cod sursa (job #904858) | Cod sursa (job #1061118) | Cod sursa (job #157279) | Cod sursa (job #2591252)
/*Sursa clean
Rezumat:
Generez cu backtracking toate posibilitatile de a face flip la linii.
Salvez si actualizez sumele pe coloane intr-un array separat.
In calculul sumei totale adun pt fiecare coloana suma mai mare
dintre flip coloana vs. no-flip coloana, adica abs(suma coloana)
Observatii:
1. In rezultatul final nu conteaza ordinea in care sunt aplicate flip-urile.
2. Doua flip-uri la aceeasi linie sau coloana se anuleaza reciproc.
*/
#include <fstream>
#include <climits>
int nrLinii, nrColoane, m[16][16], sumeColoana[16];
long long int maxSum = LLONG_MIN;
void flip(int linie) {
for (int j = 0; j < nrColoane; j++) {
m[linie][j] *= -1;
sumeColoana[j] += m[linie][j]; // pt. a anula termenul vechi
sumeColoana[j] += m[linie][j]; // pt. a aplica termenul nou
}
}
long long int matrixSum() {
long long int sum = 0;
for (int i = 0; i < nrColoane; i++) {
sum += abs(sumeColoana[i]);
}
return sum;
}
void backtrack(int linie) {
if (linie == nrLinii) {
long long int sum = matrixSum();
if (sum > maxSum) maxSum = sum;
}
else {
backtrack(linie + 1); // no flip + avansare linie urmatoare
flip(linie);
backtrack(linie + 1); // flip + avansare linie urmatoare
flip(linie); // trebuie facut flip din nou
// dupa revenire, pt. a aduce linia
// la starea dinaintea apelului recursiv
}
}
int main() {
std::ifstream fin("flip.in");
std::ofstream fout("flip.out");
fin >> nrLinii; fin >> nrColoane;
for (int i = 0; i < nrLinii; i++) {
for (int j = 0; j < nrColoane; j++) {
fin >> m[i][j];
sumeColoana[j] += m[i][j];
}
}
fin.close();
backtrack(0);
fout << maxSum;
fout.close();
return 0;
}