Cod sursa(job #2420593)

Utilizator Sonic19260Rosca Razvan Sonic19260 Data 12 mai 2019 19:36:54
Problema Jocul Flip Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>

using namespace std;

void citire();
bool schimbareLin(const int lin);
bool schimbareCol(const int col);

void backtr();

int n, m;
int a[16][16];

int main()
{
	citire();

	backtr();

	long long s = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			s += a[i][j];
		}
	}

	ofstream fout("flip.out");

	fout << s;

	fout.close();

	return 0;
}

void citire()
{
	ifstream fin("flip.in");

	fin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			fin >> a[i][j];
		}
	}

	fin.close();
}

bool schimbareLin(const int lin)
{
	long long sPoz = 0, sNeg = 0;
	for (int col = 0; col < m; col++) {
		if (a[lin][col] > 0) {
			sPoz += a[lin][col];
		}
		else {
			sNeg += a[lin][col];
		}
	}

	return sPoz < sNeg * -1;
}

bool schimbareCol(const int col)
{
	long long sPoz = 0, sNeg = 0;
	for (int lin = 0; lin < n; lin++) {
		if (a[lin][col] > 0) {
			sPoz += a[lin][col];
		}
		else {
			sNeg += a[lin][col];
		}
	}

	return sPoz < sNeg * -1;
}

void backtr()
{
	bool schimbareEfectuata;
	do {
		schimbareEfectuata = false;

		for (int i = 0; i < n; i++) {
			if (schimbareLin(i)) {
				for (int j = 0; j < m; j++) {
					a[i][j] *= -1;
				}

				schimbareEfectuata = true;
			}
		}

		for (int j = 0; j < m; j++) {
			if (schimbareCol(j)) {
				for (int i = 0; i < n; i++) {
					a[i][j] *= -1;
				}

				schimbareEfectuata = true;
			}
		}
	} while (schimbareEfectuata);
}