Cod sursa(job #509414)

Utilizator bleed310Blid Paul Filip bleed310 Data 11 decembrie 2010 00:27:47
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <iostream>
#include <fstream>

using namespace std;


/* algorithm is as follows */


/* 1. scan table horizontally, see if we can make a greater sum on any line, if yes, flip it
 * 2. scan the table vertically, see if we can make a greater sum on any column, if yes, flip it
 * 3. when no more permutations are possible we obtained the max sum */

/* checks wether or not to flip a col, and if so, flips it. */



int main()
{
	int n, m;

	
	ifstream in("flip.in");
	ofstream out("flip.out");
	in >> n >> m;

	/* allocate multi-dimensional array */
	int **table = new int*[n];
	for(int i = 0; i < 5; i++)
		table[i] = new int[m];

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
			in >> table[i][j];
	}

	int sumn = 0, sumf = 0; /* sum of current state and sum of flipped state */
	int sum = 0, lastsum = 0;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
			lastsum += table[i][j];
	}

	while(true) /* loop is broken automatically when lastsum == sum */
	{
		
		/* HORIZONTAL FLIP */
		for(int i = 0; i < n; i++) /* line id */
		{
			for(int j = 0; j < m; j++)
			{
				sumn += table[i][j];
				sumf += (table[i][j] * -1);
			}
			if(sumn < sumf)
			{
				for(int j = 0; j < m; j++)
					table[i][j] = (table[i][j] * -1);

	//			cout << "Flip line " << i + 1 << endl;
				sumn = sumf;
			}
			sumn = sumf = 0; /* reset sums */
		}

		for(int j = 0; j < m; j++)
		{
			for(int i = 0; i < n; i++)
			{
				sumn += table[i][j];
				sumf += (table[i][j] * -1);
			}

			if(sumn < sumf)
			{
				for(int i = 0; i < n; i++)
					table[i][j] = (table[i][j] * -1);
		//		cout << "Flipping row " << j + 1 << endl;
			}

			sum += sumn;
			sumn = sumf = 0;
		}

		if(lastsum == sum) /* no more possible moves */
		{
			out << sum;
			break;
		}
		lastsum = sum;
		sum = 0;
	}
}