Cod sursa(job #557480)

Utilizator tudorsTudor Siminic tudors Data 16 martie 2011 18:00:34
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <stdio.h>
#define N 505
#define INF 1000001
using namespace std;

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

int n,m;
int sl,sc,fl,fc;
int A[N][N];
int B[N][N];
PUNCT C[N*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;
	C[p].cost=0;
	while (p<=u)
	{
		x=C[p++];
		ll=x.l;
		cc=x.c;
		if (p==2)
			{
				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 && x.cost+cost(dir[i],dir[i])<B[lnou][cnou])
					{
						B[lnou][cnou]=x.cost+cost(dir[i],dir[i]);
						C[++u].l=lnou;
						C[u].c=cnou;
						C[u].ori=dir[i];
						C[u].cost=x.cost+cost(dir[i],dir[i]);
					}
				}
			}
		else
		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 && x.cost+cost(x.ori,dir[i])<B[lnou][cnou])
			{
				B[lnou][cnou]=x.cost+cost(x.ori,dir[i]);
				C[++u].l=lnou;
				C[u].c=cnou;
				C[u].ori=dir[i];
				C[u].cost=x.cost+cost(x.ori,dir[i]);
			}
		}
	}
}

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]);
	
	fclose(f);
	fclose(g);
	return 0;
}