Cod sursa(job #358743)

Utilizator andreea_alexAndreea Alexandru andreea_alex Data 24 octombrie 2009 12:06:12
Problema Jocul Flip Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>

int N,M,a[20][20];
int max,sol1[20],sol2[20];
 
void citire();
void bkt1(int);
void bkt2(int);
void pupu();
bool upup(int);
 
int main()
{
    freopen("flip.in","r",stdin);
    freopen("flip.out","w",stdout);
    citire();
    bkt1(1);
    printf("%d ", max);
    return 0;
}
 
void citire()
{
    scanf("%d%d ", &N,&M);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            scanf("%d ",&a[i][j]);
}
 
void bkt1(int p)
{
    if(p==M+1)
    {
        bkt2(1);
        return;
    }
    sol1[p]=1;
    bkt1(p+1);
    sol1[p]=-1;
    bkt1(p+1);
}
 
void pupu()
{
	int s=0;
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
			s+=a[i][j]*sol1[j]*sol2[i];
    if(s>max)
        max=s;
}
 
void bkt2(int p)
{
    if(p==N+1)
    {
        pupu();
        return;
    }
	if(upup(p))
	{
		sol2[p]=1;
		bkt2(p+1);
	}
	else
	{
		sol2[p]=-1;
		bkt2(p+1);
	}
}

bool upup(int p)
{
	int sum=0;
	for(int i=1;i<=M;++i)
		sum+=a[p][i]*sol1[i];
	if(sum>0)
		return true;
	return false;
}