Cod sursa(job #587490)

Utilizator maritimCristian Lambru maritim Data 4 mai 2011 23:30:44
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 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;
	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]])
			{
				if(B[Ci->x][Ci->y]+i<=8)
					c = abs(B[Ci->x][Ci->y]-i);
				else
					c = (B[Ci->x][Ci->y]+i)%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]);
				}
			}
		Ci = Ci->adr;
	}
}

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 ",D[i][j]);
//		fprintf(stdout,"\n");
//	}
	fprintf(g,"%d",D[st2][sf2]);
	
	fclose(g);
	fclose(f);
}