Cod sursa(job #799791)

Utilizator toranagahVlad Badelita toranagah Data 20 octombrie 2012 02:28:43
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;

ifstream fin("flip.in");
ofstream fout("flip.out");

int N, M;
int mat[17][17];
int maxRes;

void flip_row(int row);
void check_sum();
void backtraking(int row);
int abs(int a) {return a < 0 ? -a : a;}

int main() {
	fin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			fin >> mat[i][j];
		}
	}
	backtraking(1);
	fout << maxRes;
}

void backtraking(int row) {
	if (row > N) {
		check_sum();
		return;
	}
	backtraking(row + 1);
	flip_row(row);
	backtraking(row + 1);
	flip_row(row);
}

void flip_row(int row) {
	for (int j = 1; j <= M; ++j) {
		mat[row][j] *= -1;
	}
}

void check_sum() {
	int res = 0;
	for (int j = 1; j <= M; ++j) {
		int valCol = 0;
		for (int i = 1; i <= N; ++i) {
			valCol += mat[i][j];
		}
		res += abs(valCol);
	}
	if (res > maxRes) {
		maxRes = res;
	}
}