Cod sursa(job #1430832)

Utilizator Arsenescu_Mihai_Catalin_322CAArsenescu Mihai Catalin Arsenescu_Mihai_Catalin_322CA Data 8 mai 2015 21:09:04
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;
typedef vector<vector<int> > MATRIX;
typedef unsigned int uint;
vector<int> moves;
int maxi;

int get_sum(MATRIX table) {
	int sum = 0;
	for(uint i = 0; i < table.size(); i++)
		for(uint j = 0; j < table[i].size(); j++) 
			sum += table[i][j];
	return sum;
}

MATRIX make_move(int move, MATRIX table) {
	if(move < table.size()) {
		// Modify row [move]
		for(uint i = 0; i < table[move].size(); i++)
			table[move][i] *= -1;
	}
	else
		if(move >= table.size()) {
			move %= table.size();
			// Modify column [move]
			for(uint i = 0; i < table.size(); i++)
			table[i][move] *= -1;
		}
	return table;
}

void back_flip(vector<int> possible_solution, MATRIX table) {
	if(possible_solution.size() && get_sum(table) > maxi) {
		maxi = get_sum(table);
	}
	
	for(uint move = 0; move < moves.size(); move++) {
		// See if move is valid
		bool valid = true;
		for(uint i = 0; i < possible_solution.size(); i++) 
			if(move == possible_solution[i]) {
				valid = false;
				break;
			}
		if(valid) {
			possible_solution.push_back(move);
			back_flip(possible_solution, make_move(move, table));
			possible_solution.pop_back();
		}
	}	
}

int main() {
	fstream input("flip.in", ios_base::in);
	fstream output("flip.out", ios_base::out);
	int n,m;
	input >> n >> m;
	MATRIX table = vector<vector<int> >(n, vector<int>(m, 0));
	for(int i = 0; i < n; i++) 
		for(int j = 0; j < m; j++) 
			input >> table[i][j];
	for(int i = 0; i < n + m; i++)
		moves.push_back(i);
	maxi = get_sum(table);
	vector<int> solution;
	back_flip(solution, table);
	output << maxi;
	input.close();
	output.close();
	return 0;
}