Cod sursa(job #268144)

Utilizator ooctavTuchila Octavian ooctav Data 28 februarie 2009 20:32:21
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
const int N=17,M=17;
int n,m,e[17][17],max=-1000000000;
char sol[N];
void prelucrare()
{
	int s=0,i,j,slin;
	for(i=1;i<=n;++i)
	{
		slin=0;//suma pe linia i
		for(j=1;j<=m;++j)
			if(sol[j])
				slin-=e[i][j];
			else
				slin+=e[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 elem k (coloana) il luam sau nu in submultimea curenta
{
	if(k==m+1)
	{
		prelucrare();
		return;
	}
	/*
	int i;
	for(i=0;i<=1;++i)
	{
		sol[k]=i;
		back(k+1);
	}
	*/
	sol[k]=0;
	back(k+1);
	sol[k]=1;
	back(k+1);
}

void calc_sol(int x)
{
	int k=1;
	while(x)
	{
		sol[k++]=(x&1);
		x>>=1;
	}
	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 ",&e[i][j]);
	//back(1);
	for(i=0 ; i < 1<<m ; ++i)
	{
		calc_sol(i);
		prelucrare();
	}
	printf("%d\n",max);
	return 0;
}