Cod sursa(job #129978)

Utilizator pak0sebastian D pak0 Data 30 ianuarie 2008 19:41:35
Problema Jocul Flip Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
long long int n,m,i,j,a[20][20],vc[30],vl[30],x,smax=1,sn;

void rd()
{
FILE *in;
in=fopen("flip.in","r");
fscanf(in,"%ld%ld",&n,&m);
for(i=0;i<n;i++)
	for(j=0;j<m;j++)
		fscanf(in,"%ld",&a[i][j]);
fclose(in);
}
long int sl(long int x)
{
long int s=0;
for(j=0;j<m;j++)
	s+=a[x][j];
return s;
}
long int sc(long int x)
{
long int s=0;
for(i=0;i<n;i++)
	s+=a[i][x];
return s;
}
void vctr()
{
for(x=0;x<n;x++)
	vl[x]=sl(x);
for(x=0;x<m;x++)
	vc[x]=sc(x);
}

void flip(long int l,long int c)
{
	if(c==0)
		{
		for(j=0;j<m;j++)
			{
			a[l][j]*=-1;
			vl[l]+=2*a[l][j];
			vc[j]+=2*a[l][j];
			}
		}
	if(l==0)
		{
		for(i=0;i<n;i++)
			{
			a[i][c]*=-1;
			vc[c]+=2*a[i][c];
			vl[i]+=2*a[i][c];
			}
		}
}

long int mins()
{
long int min,l,c;
vctr();
while(1)
	{
	min=vl[0];
	for(i=1;i<n;i++)
		if(min>vl[i])
			{
			c=0;
			min=vl[i];
			l=i;
			}

	for(j=0;j<m;j++)
		if(min>vc[j])
			{
                        l=0;
			c=j;
			min=vc[j];
			}
        sn=0;
	flip(l,c);
	for(i=0;i<n;i++)
		sn+=vl[i];
	if(sn<=smax)
		return sn;
	smax=sn;


	}

}
void drw()
{
FILE *out;
out=fopen("flip.out","w");
fprintf(out,"%ld",mins());
fclose(out);
}
int main()
{
rd();
//printf("%ld\n",mins());
drw();
return 0;
}