Cod sursa(job #477702)

Utilizator Astrid28Ruxandra Cohal Astrid28 Data 15 august 2010 23:57:41
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#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;
}