Cod sursa(job #1751192)

Utilizator fsx1073Alex Toma fsx1073 Data 31 august 2016 21:56:22
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#include<iostream>
#include<climits>

using namespace std;

int m, n;
int **game;
int maxSum;

ifstream f("flip.in");	
ofstream g("flip.out");

void print() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << game[i][j] << "\t";
		}
		cout << endl;
	}
}

inline void invertRow(int row) {
	for (int j = 0; j < m; j++) {
		game[row][j] = -game[row][j];
	}
}

inline void invertCol(int col) {
	for (int i = 0; i < n; i++) {
		game[i][col] = -game[i][col];
	}
}

int totalSum() {
	int sum = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			sum += game[i][j];
		}
	}

	return sum;
}

void backtrackC(int start) {
	if (start == m) {
		return;
	} else {
		int x = totalSum();

		if (x > maxSum) {
			maxSum = x;
		}
	}

	for (int i = start; i < m; i++) {
		invertCol(i);
		backtrackC(i + 1);
		invertCol(i);
	}
}

void backtrackR(int start) {
	if (start == n) {
		return;
	} else {
		backtrackC(0);
	}

	for (int i = start; i < n; i++) {
		invertRow(i);
		backtrackR(i + 1);
		invertRow(i);
	}	
}

void backtrack() {
	backtrackR(0);
}

void freeAll() {
	for (int i = 0; i < n; i++) {
		delete game[i];
	}

	delete game;
}

int main() {
	f >> n >> m;

	game = new int*[n];

	for (int i = 0; i < n; i++) {
		game[i] = new int[m];
		for (int j = 0; j < m; j++) {
			f >> game[i][j];
		}
	}

	maxSum = totalSum();

	backtrack();

	g << maxSum;

	freeAll();
	return 0;
}