Cod sursa(job #275002)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 10 martie 2009 10:04:48
Problema Car Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 2.52 kb
#include<stdio.h>
#define infile "car.in"
#define outfile "car.out"
#define nmax 501
#define cmax (nmax*nmax)
#define inf (1<<30)
const int ii[]={-1,-1,-1,0,1,1,1,0};
const int jj[]={-1,0,1,1,1,0,-1,-1};
struct coada
	{
	int i,j; //pozitia in care ne aflam
	int c,t; //costul si tipul manevrei efectuate sa ajungem aici
	} c[cmax]; //coada
char h[nmax][nmax]; //harta
int d[nmax][nmax]; //matricea pentru costul minim din punctul de plecare
int n,m; //numarul de linii si coloane
int si,sj; //pozitia de start
int fi,fj; //pozitia de final

int cost_mut(int x, int y)
	{
	int z;
	if(x<0||y<0) return 0; //e atunci cand poate sa se deplaseze in orice directie
	if(x<y) { z=x; x=y; y=z; } //punem sa avem in x mai mic
	if(x-y==4) return inf; //curba 180 grade
	if(x-y==3||x-y==5) return 3; //curba la 135 grade
	if(((x-y)%4)==2) return 2; //curba la 90 grade
	if(x-y==1||x-y==7) return 1; //curba la 45 grade
	return 0; //fara curba
	}

void citire()
	{
	int i,j;
	scanf("%d %d\n",&n,&m); //nr-ul de linii si coloane
	scanf("%d %d %d %d\n",&si,&sj,&fi,&fj); //pozitia de start si sfarsit
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d",&h[i][j]); //tipul drumului de la pozitia i,j
	}

void initializare()
	{
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			d[i][j]=inf; //initial costul este infinit
	}

void bf(int i, int j)
	{
	int k,pi,pj,pc,pt,cost;
	int p,q,e; //pentru coada
	p=q=e=1; c[1].i=i; c[1].j=j; c[1].c=0; c[1].t=-1; d[i][j]=0; //initializam coada
	while(e) //cat timp avem elemente in coada
		{
		pi=c[p%cmax].i; pj=c[p%cmax].j; //pozitia din care plecam
		pc=c[p%cmax].c; pt=c[p%cmax].t; //costul, si tipul manevrei
		for(k=0;k<8;k++)
			{
			i=pi+ii[k]; j=pj+jj[k]; //pozitia vecina
			if(i>0&&i<=n&&j>0&&j<=m&&!h[i][j]) //daca pozitia e in interiorul hartii, si daca putem trece in aceasta casuta
				{
				cost=pc+cost_mut(pt,k); //costul de pana acum + costul manevrei curente
				if(cost<d[i][j]+2) //daca ajung cu un cost cu cel mult 4 mai mare
					{
					if(cost<d[i][j]) d[i][j]=cost; //daca costul este mai mic, il salvez
					//il adaugam in coada
					q++; e++; //facem loc in coada
					c[q%cmax].i=i; c[q%cmax].j=j; //salvez pozitia in coada
					c[q%cmax].c=cost; c[q%cmax].t=k; //salvez costul, si tipul manevrei
					}
				}
			}
		p++; e--; //inaintam in coada
		}
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire();
initializare();
bf(si,sj);
printf("%d",d[fi][fj]);

fclose(stdin);
fclose(stdout);
return 0;
}