Cod sursa(job #542550)

Utilizator lau08Laurentiu Capatina lau08 Data 26 februarie 2011 14:51:47
Problema Pixels Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.48 kb
#include<stdio.h>
#define NMax 101
#define MinusInf -32000
FILE *f=fopen("pixels.in","r");
FILE *g=fopen("pixels.out","w");
struct Pixel{int a,b,c[5];};
Pixel P[NMax][NMax],Pa[5];
int n,C[NMax][NMax],S[NMax][NMax];
int suma;

void Read()
{int i,j;
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	{	
		fscanf(f,"%d",&P[i][j].a);
		C[i][j]=MinusInf;
	}
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		fscanf(f,"%d",&P[i][j].b);
for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	fscanf(f,"%d %d %d %d",&P[i][j].c[1],&P[i][j].c[2],&P[i][j].c[3],&P[i][j].c[4]);

}

void Det_Noduri_valide(int x,int y)
{
if(P[x-1][y].a>=1 && C[x-1][y]==MinusInf)Pa[1]=P[x-1][y];
else Pa[1].a=0;
if(P[x][y-1].a>=1 && C[x][y-1]==MinusInf)Pa[4]=P[x][y-1];
else Pa[4].a=0;
if(P[x][y+1].a>=1 && C[x][y+1]==MinusInf)Pa[2]=P[x][y+1];
else Pa[2].a=0;
if(P[x+1][y].a>=1 && C[x+1][y]==MinusInf)Pa[3]=P[x+1][y];
else Pa[3].a=0;
}

int Verif_amanuntita(int x,int y,int s,int sw)//t reprezinta pozitia elementului de la care a plecat
{int saux=s;
	if(sw*S[x-1][y]<0 && C[x-1][y]!=MinusInf)//comparatia cu elem de sus
		saux-=P[x-1][y].c[3];
	if(sw*S[x][y+1]<0 && C[x][y+1]!=MinusInf)//comparatia cu elem din dreapta
		saux-=P[x][y+1].c[4];
	if(sw*S[x+1][y]<0 && C[x+1][y]!=MinusInf)//comparatia cu elem de jos
		saux-=P[x+1][y].c[1];
	if(sw*S[x][y-1]<0 && C[x][y-1]!=MinusInf)//comparatia cu elem din stanga
		saux-=P[x][y-1].c[2];
return saux;
}

void Solve(int x,int y,int sw)
{int s[5],i,max=MinusInf,k,sww[5],ok=0;
for(i=1;i<=4;i++)
	s[i]=MinusInf;
Det_Noduri_valide(x,y);
for(i=1;i<=4;i++)
if(Pa[i].a>=1)	
	{ok=1;
	int xc,yc,m1,m2;
	if(i==1){xc=x-1; yc=y;}
			else if(i==2){xc=x;yc=y+1;}
			else if(i==3){xc=x+1; yc=y;}
			else if(i==4){xc=x; yc=y-1;}
			
		m1=Verif_amanuntita(xc,yc,Pa[i].a,1);
		m2=Verif_amanuntita(xc,yc,Pa[i].b,-1);
		if(m1>m2){s[i]=m1; sww[i]=1;}
		else {s[i]=m2; sww[i]=-1;}
	
	}
if(ok==1)
{
	for(i=1;i<=4;i++)
		if(max<s[i])
		{	max=s[i]; k=i; sw=sww[i];}
	suma+=max;
	if(k==1) {C[x-1][y]=max;S[x-1][y]=sw; Solve(x-1,y,sw);}
	else if(k==2) {C[x][y+1]=max;S[x][y+1]=sw; Solve(x,y+1,sw);}
		else if(k==3) {C[x+1][y]=max;S[x+1][y]=sw; Solve(x+1,y,sw);}
			else if(k==4) {C[x][y-1]=max;S[x][y-1]=sw; Solve(x,y-1,sw);}
}
}
int main()
{int sw;
Read();
if(P[n][n].a>P[n][n].b)
	{C[n][n]=P[n][n].a; sw=1;}
else {C[n][n]=P[n][n].b; sw=-1;}
suma=C[n][n];
S[n][n]=sw;
Pa[1]=P[n-1][n];
Pa[4]=P[n][n-1];
Pa[2].a=Pa[3].a=0;
Solve(n,n,sw);
fprintf(g,"%d\n",suma);
return 0;
}