Cod sursa(job #556102)

Utilizator tudorsTudor Siminic tudors Data 15 martie 2011 22:22:58
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <stdio.h>
#define N 501
#define INF 100001
using namespace std;

typedef struct {int l,c,ori;} PUNCT; 

int n,m,salvez,prima=1;
int sl,sc,fl,fc;
int A[N][N];
int B[N][N];
PUNCT C[50*N];

int dl[8]={-1,-1,0,1,1,1,0,-1};
int dc[8]={0,1,1,1,0,-1,-1,-1};
int dir[8]={1,2,3,4,5,6,7,8};

FILE *f, *g;

void citire()
{
	int i,j;
	fscanf(f,"%d %d",&n,&m);
	fscanf(f,"%d %d %d %d",&sl,&sc,&fl,&fc);
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			fscanf(f,"%d",&A[i][j]);
}

int cost(int ori, int dir)
{
	if (ori==1)
	{
		if (dir==2 || dir==8)
			return 1;
		else if (dir==3 || dir==7)
			return 2;
		else if (dir==4 || dir==6)
			return 3;
		else if (dir==1)
			return 0;
		else return 4;
	}
	else if (ori==2)
		{
			if (dir==1 || dir==3)
				return 1;
			else if (dir==8 || dir==4)
				return 2;
			else if (dir==7 || dir==5)
				return 3;
			else if (dir==2)
				return 0;
			else return 4;
		}
	else if (ori==3)
		{
			if (dir==2 || dir==4)
				return 1;
			else if (dir==1 || dir==5)
				return 2;
			else if (dir==8 || dir==6)
				return 3;
			else if (dir==3)
				return 0;
			else return 4;
		} 
	else if (ori==4)
		{
			if (dir==3 || dir==5)
				return 1;
			else if (dir==2 || dir==6)
				return 2;
			else if (dir==1 || dir==7)
				return 3;
			else if (dir==4)
				return 0;
			else return 4;
		}
	else if (ori==5)
		{
			if (dir==4 || dir==6)
				return 1;
			else if (dir==3 || dir==7)
				return 2;
			else if (dir==2 || dir==8)
				return 3;
			else if (dir==5)
				return 0;
			else return 4;
		}
	else if (ori==6)
		{
			if (dir==5 || dir==7)
				return 1;
			else if (dir==4 || dir==8)
				return 2;
			else if (dir==1 || dir==3)
				return 3;
			else if (dir==6)
				return 0;
			else return 4;
		}
	else if (ori==7)
		{
			if (dir==8 || dir==6)
				return 1;
			else if (dir==1 || dir==5)
				return 2;
			else if (dir==2 || dir==4)
				return 3;
			else if (dir==7)
				return 0;
			else return 4;
		}
	else if (ori==8)
		{
			if (dir==1 || dir==7)
				return 1;
			else if (dir==2 || dir==6)
				return 2;
			else if (dir==3 || dir==5)
				return 3;
			else if (dir==8)
				return 0;
			else return 4;
		}
	return 0;
}

void lee(int l, int c)
{
	int i,p,j,u,ll,cc,lnou,cnou;
	PUNCT x;
	for (i=1;i<=n;++i)
		for (j=1;j<=m;++j)
			B[i][j]=INF;
	B[l][c]=0;
	p=u=1;
	C[p].l=l;
	C[p].c=c;
	C[p].ori=1;
	while (p<=u)
	{
		x=C[p++];
		ll=x.l;
		cc=x.c;
		for (i=0;i<=7;++i)
		{
			lnou=ll+dl[i];
			cnou=cc+dc[i];
			if (A[lnou][cnou]==0 && lnou>=1 && lnou<=n && cnou>=1 && cnou<=m && B[ll][cc]+cost(x.ori,dir[i])<B[lnou][cnou])
			{
				B[lnou][cnou]=B[ll][cc]+cost(x.ori,dir[i]);
				C[++u].l=lnou;
				C[u].c=cnou;
				C[u].ori=dir[i];
				if (prima==1)
				{
					prima=0;
					salvez=B[lnou][cnou];
				}
			}
		}
	}
}

int main()
{
	f=fopen("car.in","r");
	g=fopen("car.out","w");
	
	citire();
	lee(sl,sc);
	if (B[fl][fc]==INF)
		fprintf(g,"-1");
	else
		fprintf(g,"%d",B[fl][fc]-salvez);
	
	fclose(f);
	fclose(g);
	return 0;
}