Cod sursa(job #12461)

Utilizator airineivAirinei Vasile airineiv Data 3 februarie 2007 22:54:34
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include "stdio.h"
#include "math.h"
int N, M;
int a[16][16];
char binar[17];

void reprez_binar(int n)
{
	int k=0;
	for(int i=0; i<N; i++)
		binar[i] = '0';
	while(n)
	{
		if(n%2==1)
			binar[N-1-k] = '1';
		n=n/2;
		k++;
	}
	binar[N]='\0';
}
void comuta_row(int row)
{
	int col;
	for(col=0; col<M; col++)
		a[row][col] *= -1;
}
void comuta_col(int col)
{
	int row;
	for(row=0; row<N; row++)
		a[row][col] *= -1;
}
int suma(void)
{
	int row, col;
	int suma = 0;
	for(row=0; row<N; row++)
		for(col=0; col<M; col++)
		{
			suma += a[row][col];
		}
	return suma;
}

int main(void)
{
	FILE *fin, *fout;
	
	int i,j, pow=1, k;
	
	if((fin = fopen("flip.in", "r"))==NULL)
		return -1;
	if((fout = fopen("flip.out", "w"))==NULL)
		return -1;
	fscanf(fin, "%d %d", &N, &M);
	for(k=0;k<N;k++)
		pow *= 2;
	int *sume_linii[16];	
	for(k=0; k<N; k++)
		sume_linii[k] = new int[pow];
	for(i=0; i<N; i++)
	{
		sume_linii[i][0]=0;
		for(j=0; j<M; j++)
		{
			fscanf(fin, "%d", &a[i][j]);
			sume_linii[i][0] += a[i][j];
		}
	}
	
	for(k=1; k<pow; k++)
	{
		reprez_binar(k);
		for(int i=0; binar[i] != '\0'; i++)
		{
			if(binar[i]=='1')
				sume_linii[i][k] = -sume_linii[i][0];
			else
				sume_linii[i][k] = sume_linii[i][0];
		}
	}
	int comb_max = 0;
	int max=0;
	for(i=0; i<N; i++)
		max+=sume_linii[i][0];
	for(k=1; k<pow; k++)
	{
		int sum = 0;
		for(i=0; i<N; i++)
			sum+=sume_linii[i][k];
		if(max<sum)
		{
			max=sum;
			comb_max=k;
		}
	}
	reprez_binar(comb_max);
	for(i=0; i<N; i++)
	{
		if(binar[i] == '1')
			comuta_row(i);
	}
	for(j=0; j<M; j++)
	{
		int sum=0;
		for(i=0; i<N; i++)
			sum+=a[i][j];
		if(sum<0)
			comuta_col(j);
	}
	for(k=0; k<N; k++)
	{
		delete []sume_linii[k];
		sume_linii[k] = NULL;
	}
	fprintf(fout, "%d\n", suma());
	fclose(fin);
	fclose(fout);
	return 0;
}