Cod sursa(job #610157)

Utilizator IgnitionMihai Moraru Ignition Data 25 august 2011 12:30:03
Problema Jocul Flip Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MN (16)

int main()
{
	freopen("flip.in", "r", stdin);
	freopen("flip.out", "w", stdout);

	int n[MN][MN], N, M;
	int i, j;

	scanf("%d %d", &N, &M);

	for(i = 0; i < N; ++i) for(j = 0; j < M; ++j)
		scanf("%d", &n[i][j]);

	/*
	 * We are going to do backtracking either on rows or on columns,
	 * so choose the smaller of the two.
	 */
	if(M < N) {
		// Transpose the matrix
		int naux[MN][MN];
		for(i = 0; i < N; ++i) for(j = 0; j < M; ++j)
			naux[j][i] = n[i][j];
		memcpy(n, naux, sizeof(n));
		// Swap N and M
		int tmp = N;
		N = M;
		M = tmp;
	}

	// Debug
	/*
	for(i = 0; i < N; ++i) {
		for(j = 0; j < M; ++j)
			printf("%d ", n[i][j]);
		printf("\n");
	}
	*/

	int sw[MN] = {-1}; // whether the row is switched or not (multiplied by -1)
	int k; // the position in the backtracking (we simulate the stack because it's iterative bkt)
	int s, S = INT_MIN, scol; // current sum, best sum, column sum

	for(k = 0; k >= 0; ) {
		if(k >= N) { // We have a candidate
			// Adjust the columns to have the optimum sum for this configuration of rows
			s = 0;
			for(j = 0; j < M; ++j) {
				for(scol = i = 0; i < N; ++i)
					scol += sw[i]? -n[i][j] : n[i][j];
				s += scol >= 0? scol : -scol;
			}
			// Did we beat the record?
			if(s > S)
				S = s;
		}
		++sw[k]; // next choice at this level
		if(sw[k] > 1)
			--k; // backtrack (or pop off the stack)
		else { // advance (push onto the stack)
			if(++k < N)
				sw[k] = -1;
		}
	}

	// Brute-force is over, time to tell the ladies and gentlemen our results
	printf("%d\n", S);

	return 0;
}