Cod sursa(job #1426653)

Utilizator DRaduDaniel Radu DRadu Data 30 aprilie 2015 10:04:49
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
//#define CONSOLE_MODE 1

#if CONSOLE_MODE
#include <iostream>
#else
#include <fstream>
#endif

#include <stack>
#include <limits>

using namespace std;

int getmax(int m, int n, int flip[16][16])
{
	int k = 0;
	int maxSum = INT_MIN, currentSum = 0;

	bool isFlipped[16];

	while (k>=0)
	{
		while (k < m)
		{
			k++;
			if (k < m)
				isFlipped[k] = false;
		}

		k--;

		if (k == m - 1)
		{
			currentSum = 0;
			int aux_flip[16][16];
			//copy array for safety
			for (int i = 0; i < m; i++)
			{
				for (int j = 0; j < n; j++)
				{
					aux_flip[i][j] = flip[i][j];
				}
			}

			//make all the flipping for the elements in the stack/array
			for (int i = 0; i < m; i++)
			{
				int factor = isFlipped[i] ? -1 : 1;
				
				for (int j = 0; j < n; j++)
				{
					aux_flip[i][j] = factor * aux_flip[i][j];
				}
			}


			//make all the flipping on the columns (if sum(col) < 0 then flip)

			for (int j = 0; j < n; j++)
			{
				int colsum = 0;
				for (int i = 0; i < m; i++)
				{
					colsum += aux_flip[i][j];
				}

				if (colsum < 0)
				{
					for (int i = 0; i < m; i++)
						aux_flip[i][j] = -1 * aux_flip[i][j];
				}
			}

			//compute the actual sum
			for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				currentSum += aux_flip[i][j];


			if (maxSum < currentSum)
			{
				maxSum = currentSum;
			}
		}

		while (isFlipped[k] && k >= 0)
		{
			k--;
		}

		if (k >= 0)
		{
			isFlipped[k] = true;
		}


	}

	return maxSum;
}

int main()
{
	int m, n;
	int flip[16][16];

#if CONSOLE_MODE
	std::cin >> m >> n;
	for (int i = 0; i < m; i++)
	for (int j = 0; j < n; j++)
		std::cin >> flip[i][j];
#else
	ifstream IN("flip.in");
	IN >> m >> n;
	for (int i = 0; i < m; i++)
	for (int j = 0; j < n; j++)
		IN >> flip[i][j];
	IN.close();
#endif

#if CONSOLE_MODE
	cout << getmax(m, n, flip) << endl;
	system("pause");
#else
	ofstream OUT("flip.out");
	OUT << getmax(m, n, flip) << endl;
	OUT.close();
#endif
	return 0; 
}