Cod sursa(job #268143)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 februarie 2009 20:32:19
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
int n,m;
int matrice[17][17],max=-1000000000;
char sol[17];
void prelucrare()
{
	int s=0,i,j,slin;//suma pe prima linie
	for (i=1; i<=n; ++i)
	{
		slin=0;
		for (j=1; j<=m; j++)
			if (sol[j])
				slin-=matrice[i][j];
			else
				slin+=matrice[i][j];
	    if (slin<0)//s=suma pe matrice
			s-=slin;
		else
			s+=slin;
	}
	if (s>max)
		max=s;
}
void back(int k) //alegem daca  pe elementul k(coloana) il luam sau nu in submultime curenta 
{
	if (k==m+1)
	{
		prelucrare();
		return;
	}
	int i;
	for (i=0; i<=1; ++i)
	{
		sol[k]=i;
		back(k+1);
	}
}
void calc_sol(int x)
{
	int k=1;
	while (x)
	{
		sol[k++]=x%2;
		x/=2;
	}
	while (k<=m)
		sol[k++]=0;
}
int main()
{
	freopen("flip.in","r",stdin);
	freopen("flip.out","w",stdout);
	int i,j;
	scanf("%d%d",&n,&m);
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++)
			scanf("%d",&matrice[i][j]);
	//back(1);	
	for (i=0; i<=1<<m; ++i)
	{
		calc_sol(i);
		prelucrare();
	}
	printf("%d",max);
	return 0;
}