Cod sursa(job #1225684)

Utilizator Florin93Balint florin Florin93 Data 3 septembrie 2014 13:20:15
Problema Jocul Flip Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <fstream>

using namespace std;

int matrix[18][18];
int sum;

void FlipColumn(int i,int lines)
{
	for (int j = 0; j < lines; j++)
	{
		sum -= 2 * matrix[j][i];
		matrix[j][i] = -matrix[j][i];
	}
}

void FlipLine(int j,int columns)
{
	for (int i = 0; i < columns; i++)
	{
		sum -= 2 * matrix[j][i];
		matrix[j][i] = -matrix[j][i];		
	}
}

int sum_matrix(int n, int m)
{
	int sum = 0;
	for (int i = 0; i < n;i++)
	{
		for (int j = 0; j < m; j++)
			sum += matrix[i][j];
	}
	return sum;
}


//backtrack
int FindMax(int n,int m,int currentLine,int currentColumn)
{
	int max = sum;
	for (int i = currentLine; i < n; i++)
	{
		for (int j = currentColumn; j < m; j++)
		{
			int nextMax = FindMax(n, m, currentLine + 1, currentColumn);
			if (max < nextMax) max = nextMax;

			nextMax = FindMax(n, m, currentLine, currentColumn + 1);
			if (max < nextMax) max = nextMax;

			FlipLine(i,m);			
			nextMax = FindMax(n, m, currentLine + 1, currentColumn);
			if (max < nextMax) max = nextMax;
			FlipLine(i, m);

			FlipColumn(j,n);
			nextMax = FindMax(n, m, currentLine, currentColumn+1);
			if (max < nextMax) max = nextMax;
			FlipColumn(j, n);
		}
	}

	return max;
}


int Flip(int n,int m)
{
	int max = INT_MIN;
	sum = sum_matrix(n, m);

	max = FindMax(n, m, 0, 0);

	return max;
}


int main()
{
	int n, m;

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

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

	int max = Flip(n, m);

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

	return 0;
}