Cod sursa(job #587531)

Utilizator maritimCristian Lambru maritim Data 5 mai 2011 01:04:25
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct _nod
{
	int x;
	int y;
	struct _nod *adr;
} nod;

int A[510][510];
int B[510][510];
int D[510][510];
int X[9] = {0,-1,-1,0,1,1,1,0,-1};
int Y[9] = {0,0,1,1,1,0,-1,-1,-1};
int N;
int M;
int st1;
int sf1;
int st2;
int sf2;
int c;

void add(nod*& Cf,int a,int b)
{
	nod *nou = (nod*)malloc(sizeof(nod));
	nou->x = a;
	nou->y = b;
	nou->adr = NULL;
	Cf->adr = nou;
	Cf = nou;
}

void complet(nod*& Cf,int a,int b)
{
	int x = Cf->x;
	int y = Cf->y;
	A[x][y] = 1;
	for(int i=1;i<=8;i++)
		if(!A[x+X[i]][y+Y[i]])
			{
				A[x+X[i]][y+Y[i]] = 1;
				B[x+X[i]][y+Y[i]] = i;
				add(Cf,x+X[i],y+Y[i]);
			}
}

void parc(void)
{
	nod *Ci = (nod*)malloc(sizeof(nod));
	Ci->x = st1;
	Ci->y = sf1;
	Ci->adr = NULL;
	nod *Cf = Ci;
	complet(Cf,Ci->x,Ci->y);
	Ci = Ci->adr;
	int a;
	int b;
	while(Ci)
	{
		for(int i=1;i<=8;i++)
			if(Ci->x && Ci->y && Ci->x<=N && Ci->y<=M && !A[Ci->x+X[i]][Ci->y+Y[i]])
			{
				a = B[Ci->x][Ci->y];
				b = i;
				if(abs(b-a)<-abs(a-b)+8)
					c = abs(b-a);
				else
					c = -abs(a-b)+8;
				if(!D[Ci->x+X[i]][Ci->y+Y[i]] || D[Ci->x+X[i]][Ci->y+Y[i]]>D[Ci->x][Ci->y]+c)
				{
					D[Ci->x+X[i]][Ci->y+Y[i]] = D[Ci->x][Ci->y]+c;
					B[Ci->x+X[i]][Ci->y+Y[i]] = i;
					add(Cf,Ci->x+X[i],Ci->y+Y[i]);
				}
			}
		nod *q = Ci;
		Ci = Ci->adr;
		free(q);
	}
}

int main()
{
	FILE *f = fopen("car.in","r");
	FILE *g = fopen("car.out","w");
	
	fscanf(f,"%d %d",&N,&M);
	fscanf(f,"%d %d %d %d",&st1,&sf1,&st2,&sf2);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=M;j++)
			fscanf(f,"%d",&A[i][j]);
	parc();
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
			printf("%2d ",B[i][j]);
		fprintf(stdout,"\n");
	}
	if(!D[st2][sf2])
		fprintf(g,"-1");
	else
		fprintf(g,"%d",D[st2][sf2]);
	
	fclose(g);
	fclose(f);
}