Pagini recente » Cod sursa (job #1033958) | Cod sursa (job #831451) | Cod sursa (job #1483150) | Cod sursa (job #1285803) | Cod sursa (job #832756)
Cod sursa(job #832756)
#include <stdio.h>
#include <math.h>
#include <limits.h>
#define MAXN 16
#define MAXM 16
int n, m, sum = INT_MIN;
int lineflip[MAXN] = {0};
int colflip[MAXM] = {0};
int a[MAXN][MAXM], backup[MAXN][MAXM];
// save a backup for a matrix
void copy()
{
int i, j;
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
backup[i][j] = a[i][j];
}
// restore a matrix to original state
void copy_r()
{
int i, j;
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
a[i][j] = backup[i][j];
}
// binary addition for flip vectors
void binary_add(int *flip, int n)
{
n -= 1;
while (1)
{
flip[n] += 1;
flip[n] %= 2;
if (flip[n] == 0) n--;
else
break;
}
}
// flip line
void mul_line(int i)
{
int j;
for (j = 0; j < m; j++)
a[i][j] *= -1;
}
// flip col
void mul_col(int j)
{
int i;
for (i = 0; i < n; i++)
a[i][j] *= -1;
}
// calculate current matrix sum
int matrix_sum()
{
int i, j, sum = 0;
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
sum += a[i][j];
return sum;
}
/**
* print_matrix
* used for debugging
*/
void print_matrix()
{
int i, j;
for(i = 0; i < n; i++)
{
for(j = 0; j < m; j++)
printf("%d ", a[i][j]);
printf("\n");
}
}
/**
* print_flip
* used for debugging
*/
void print_flip(int *flip, int n)
{
int i;
for(i = 0; i < n; i++)
{
printf("%d", flip[i]);
}
//printf("\n");
}
int main()
{
int i, j;
freopen ("flip.in", "r", stdin);
scanf("%d %d",&n ,&m);
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
scanf("%d", &a[i][j]);
copy();
/**
* taking a very ugly approach here
* this code generates ALL flip posibilities
* and most of them repeats over and over again
*
* this approach won't work for 100 points
*/
for(i = 0; i < pow(2, n); i++)
{
/*
print_flip(lineflip, n);
printf("\n");
*/
for(j = 0; j < pow(2, m); j++)
{
copy_r();
// do the flips
int k;
for (k = 0; k < n; k++)
if(lineflip[k]) mul_line(k);
for (k = 0; k < m; k++)
if(colflip[k]) mul_col(k);
// search for max sum
if(matrix_sum() > sum) sum = matrix_sum();
/* used for debugging
printf("%d ", matrix_sum());
print_flip(colflip, m);
printf("-");
print_flip(lineflip, n);
printf("\n");
print_matrix();
printf(" ");
print_flip(colflip, m);
printf("\n");
*/
binary_add(colflip, m);
}
binary_add(lineflip, n);
}
freopen("flip.out", "w", stdout);
printf("%d\n", sum);
return 0;
}