Cod sursa(job #2591252)

Utilizator RobertLISARURobert Lisaru RobertLISARU Data 30 martie 2020 02:56:02
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
/*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;
}