Cod sursa(job #1225765)

Utilizator Florin93Balint florin Florin93 Data 3 septembrie 2014 16:12:37
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <fstream>

using namespace std;


int** matrix;
int solution;
int* switcher;

void verify(int n,int m)
{
	int S = 0;
	for (int i = 0; i < n ; i++)
	{
		int s = 0;
		for (int j = 0; j < m; j++)
		{
			if (switcher[j]) s += matrix[i][j];
			else s -= matrix[i][j];
		}

		if (s < 0) S -= s;
		else S += s;
	}

	if (S > solution) solution = S;
}


//backtrack
void FindMax(int k,int n,int m)
{
	if (k == m)
	{
		verify(n,m);
	}
	else
	{
			switcher[k] = 0;
			FindMax(k + 1,n,m);
		
			switcher[k] = 1;
			FindMax(k + 1, n, m);
	}
}


void Flip(int n,int m)
{
	solution = INT_MIN;
	FindMax(0, n, m);
}


int main()
{
	int n, m;
	
	

	ifstream reader;
	reader.open("flip.in");
	reader >> n >> m;

	matrix = new int*[n];
	for (int i = 0; i < n; ++i)
		matrix[i] = new int[m];

	switcher = new int[m];

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			reader >> matrix[i][j];		
	}
	reader.close();

    Flip(n, m);

	ofstream writter;
	writter.open("flip.out");
	writter << solution;
	writter.close();	

	return 0;
}