Pagini recente » Cod sursa (job #2326286) | Cod sursa (job #1740709) | Cod sursa (job #249215) | Cod sursa (job #1632185) | Cod sursa (job #477702)
Cod sursa(job #477702)
#include<iostream>
#include<fstream>
#define MAX 17
using namespace std;
ifstream fin("flip.in");
ofstream fout("flip.out");
int n, m;
long a[MAX][MAX];
long smax, suma_linie[MAX], suma_coloana[MAX];
int poz[MAX];
void citire()
{
int i, j;
fin >> n >> m;
for( i=1; i<=n; i++ )
for( j=1; j<=m; j++ )
{
fin >> a[i][j];
suma_linie[i] += a[i][j];
suma_coloana[j] += a[i][j];
}
fin.close();
}
//folosesc functia dupa ce am terminat de facut flip pe coloane
void flip_linie()
{
int i;
long suma=0;
for ( i=1; i<=n; i++ )
if ( suma_linie[i] >= 0 )
suma+= suma_linie[i];
else
suma-= suma_linie[i];
if ( suma > smax )
smax = suma;
}
void flip_coloana( int k )
{
int i;
for ( i=1; i<=n; i++ )
{
a[i][k] = -a[i][k];
suma_linie[i]+= (2 * a[i][k] );
}
}
//det. toate configuratiile matricei daca se face flip pt. nr_col_flip coloane
void bkt( int nr_col_flip, int k )
{
int i;
if( k<=nr_col_flip )
{
for( i = poz[k-1] + 1; i<=m; i++ )
{
poz[k] = i;
//aplic flip pt. coloana i
flip_coloana(i);
bkt( nr_col_flip, k+1 );
//aplic din nou flip pt. coloana i pt. a ma intoarce la config. initiala
flip_coloana(i);
}
}
else
//cand am terminat de facut flip pe cele nr_col_flip coloane, aplic flip pe linii
flip_linie();
}
int main()
{
int i;
citire();
for ( i=1; i<=m; i++ )
bkt( i, 1 );
fout << smax << endl;
return 0;
}