Cod sursa(job #542372)

Utilizator udrescu_cristiUdrescu Cristian udrescu_cristi Data 26 februarie 2011 12:40:03
Problema Pixels Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.92 kb
#include<stdio.h>

#define nmax 101

 int a[nmax][nmax],i,j,n,c[10001][5];
 int t,dl[5],dc[5],k,lv,cv,lv1,cv1,mat[nmax][nmax],x,x1;
 int max,s1,s2,s,d[nmax][nmax],z,b[nmax][nmax];
 
  int main()
{
  freopen("pixels.in","r",stdin);
  freopen("pixels.out","w",stdout);
  
   scanf("%d\n",&n);
   for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
		   scanf("%d",&a[i][j]);
   for(i=1;i<=n;i++)
	   for(j=1;j<=n;j++)
		   scanf("%d",&b[i][j]);
	for(i=1;i<=n*n;i++)
	   for(j=1;j<=4;j++)
		   scanf("%d",&c[i][j]);
	   
    if(n==2)
	{
		s1=a[1][1]+a[1][2]+a[2][1]+a[2][2];
		if(s1>max) max=s1;
		s1=a[1][1]+b[1][2]+a[2][1]+a[2][2]-c[2][4]-c[2][3];
		if(s1>max) max=s1;
		s1=b[1][1]+a[1][2]+a[2][1]+a[2][2]-c[1][2]-c[1][3];
		if(s1>max) max=s1;
		s1=a[1][1]+a[1][2]+b[2][1]+a[2][2]-c[3][2]-c[3][1];
		if(s1>max) max=s1;
		s1=a[1][1]+a[1][2]+a[2][1]+b[2][2]-c[4][4]-c[4][1];
		if(s1>max) max=s1;
		
		s1=b[1][1]+b[1][2]+a[2][1]+a[2][2]-c[1][3]-c[2][3];
		if(s1>max) max=s1;
		s1=b[1][1]+a[1][2]+b[2][1]+a[2][2]-c[1][2]-c[3][2];
		if(s1>max) max=s1;
		s1=a[1][1]+b[1][2]+b[2][1]+a[2][2]-c[2][4]-c[2][3]-c[3][1]-c[3][2];
		if(s1>max) max=s1;
		s1=b[1][1]+a[1][2]+a[2][1]+b[2][2]-c[1][2]-c[1][3]-c[4][4]-c[4][1];
		if(s1>max) max=s1;
		s1=a[1][1]+b[1][2]+a[2][1]+b[2][2]-c[2][4]-c[4][4];
		if(s1>max) max=s1;
		s1=a[1][1]+a[1][2]+b[2][1]+b[2][2]-c[3][1]-c[4][1];
		if(s1>max) max=s1;
		
		s1=b[1][1]+b[1][2]+b[2][1]+a[2][2]-c[4][4]-c[4][1];
		if(s1>max) max=s1;
		s1=a[1][1]+b[1][2]+b[2][1]+b[2][2]-c[1][3]-c[1][2];
		if(s1>max) max=s1;
		s1=b[1][1]+a[1][2]+b[2][1]+b[2][2]-c[2][4]-c[2][3];
		if(s1>max) max=s1;
		s1=b[1][1]+b[1][2]+a[2][1]+b[2][2]-c[3][1]-c[3][2];
		if(s1>max) max=s1;
		s1=b[1][1]+b[1][2]+b[2][1]+b[2][2];
		if(s1>max) max=s1;
		
		printf("%d\n",max);
	}
	
	else
	{
		dl[1]=0; dc[1]=1;
		dl[2]=0; dc[2]=-1;
		dl[3]=1; dc[3]=0;
		dl[4]=-1; dc[4]=0;
		
	  for(i=0;i<=n+1;i++)
	  {
		d[i][0]=d[i][n+1]=-1;
		d[0][i]=d[n+1][i]=-1;
	  }
	  
	 k=1;
	 if(a[1][1]>b[1][1])
	  {
		  s=a[1][1];
		  mat[1][1]=0;
	 }
	 else
		{
			s=b[1][1];
        	mat[1][1]=1;
     	 }
	d[1][1]=k;
    
	do
	{
		t=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
	 if(d[i][j]==k)
	 {
		for(x=1;x<=4;x++)
		{
			lv=i+dl[x];
			cv=j+dc[x];
		if(d[lv][cv]==0)
		{
		  t=1;
		  s1=a[lv][cv];
		  s2=b[lv][cv];
		  for(x1=1;x1<=4;x1++)
		{
			lv1=lv+dl[x];
			cv1=cv+dc[x];
        if(d[lv1][cv1])
		{
			  if(dc[x1]==0)
				  if(dl[x1]==-1)
					  z=1;
				  else
					  z=3;
			  if(dl[x1]==0)
				  if(dc[x1]==-1)
	              	  z=4;
				  else
					  z=2;
		if(mat[lv1][cv1]==0) 
		  {		  
			  s2-=c[n*(lv-1)+cv][z];
		}
		else
			s1-=c[n*(lv-1)+cv][z];
		}
		  }
		if(s1>s2) {
			mat[lv][cv]=0;
      		s+=s1;
		    }			
		else
		{
			mat[lv][cv]=1;
			s+=s2;
		}
		d[lv][cv]=k+1;
		}
	}
	 }
	if(t) k++;
	 }
 while(t);

  printf("%d\n",s);
	}
return 0;
	}