Pagini recente » Cod sursa (job #2932446) | Cod sursa (job #427367) | Cod sursa (job #3221812) | Cod sursa (job #2415913) | Cod sursa (job #610157)
Cod sursa(job #610157)
#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;
}