Pagini recente » Cod sursa (job #133112) | Cod sursa (job #683757) | Cod sursa (job #138302) | Cod sursa (job #1948780) | Cod sursa (job #1460769)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
FILE *in,*out;
int m, n, i, j, k, aux;
int a[18][18], b[18][18], s_line[18], aux_line[18];
long long sum, sum_aux;
void prep_data() //transpunere 'a'
{
if (m > n)
{
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
b[j][i] = a[i][j];
a[i][j] = 0;
}
aux = m;
m = n;
n = aux;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
a[i][j] = b[i][j];
}
}
int main()
{
in=fopen("flip.in","r");
out=fopen("flip.out","w");
fscanf(in,"%d %d",&n,&m);
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
fscanf(in,"%d",&a[i][j]);
prep_data(); //in caz ca-i nevoie de transpunere; backtrack dupa dimensiunea mai mica dintre m si n
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
s_line[i] += a[i][j];
sum += a[i][j];
}
}
for (k = 1; k < (1 << m); k++)
{
sum_aux = 0;
memcpy(aux_line, s_line, 18*sizeof(int));
for (j = 1; j <= m; j++)
{
if ((1 << (j-1)) & k) //flip coloana j
{
for (i = 1; i <= n; i++)
{
aux_line[i] -= (2*a[i][j]); //diferenta intre + a[i][j] si - a[i][j] este de 2*a[i][j]
}
}
}
for (i = 1; i <= n; i++)
{
if (aux_line[i] < 0)
{
aux_line[i] *= -1; //flip linia i
}
sum_aux += aux_line[i];
}
if (sum_aux > sum)
sum = sum_aux;
}
fprintf(out,"%lld",sum);
fclose(in);
fclose(out);
return 0;
}