Cod sursa(job #361876)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 6 noiembrie 2009 22:40:36
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <cstdio>
#include <cstring>

#define file_in "car.in"
#define file_out "car.out"

#define Nmax 550

int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};

int move[8][8]={
	{0,1,2,3,4,3,2,1},
	{1,0,1,2,3,4,3,2},
	{2,1,0,1,2,3,4,3},
	{3,2,1,0,1,2,3,4},
	{4,3,2,1,0,1,2,3},
	{3,4,3,2,1,0,1,2},
	{2,3,4,3,2,1,0,1},
	{1,2,3,4,3,2,1,0}
};

int n,m;
int xi,yi,xf,yf;
int a[Nmax][Nmax];
int cost[Nmax][Nmax];
int lne,cne,xx,yy;
int qx[2*Nmax*Nmax];
int qy[2*Nmax*Nmax];
int d[Nmax][Nmax];
				
void citire()
{
	int i,j;
	freopen(file_in,"r",stdin);
	//freopen(file_out,"w",stdout);
	
	scanf("%d %d\n", &n, &m);
	scanf("%d %d %d %d\n", &xi, &yi, &xf, &yf);
	for (i=1;i<=n;++i)
		 for (j=1;j<=m;++j)
		 {
			 scanf("%d", &a[i][j]);
			 cost[i][j]=0x3f3f3f3f;
			 a[i][j]=1-a[i][j];
		 }
}

void solve()
{
	int p,u,k;
	p=1;
	u=1;
	qx[1]=xi;
	qy[1]=yi;
	
	cost[xi][yi]=0;
	
	while(p<=u)
	{
		xx=qx[p];
		yy=qy[p++];
		
		for (k=0;k<8;++k)
		{
			lne=dx[k]+xx;
			cne=dy[k]+yy;
			
			if (a[lne][cne]==1)
			{
				if (cost[lne][cne]>cost[xx][yy]+move[d[xx][yy]][k])
				{
					cost[lne][cne]=cost[xx][yy]+move[d[xx][yy]][k];
					qx[++u]=lne;
					qy[u]=cne;
					d[lne][cne]=k;
				}
			}
		}
	}
	
	
}


int main()
{
	int i,j;
	citire();
	solve();


	if (cost[xf][yf]==0x3f3f3f3f)
		printf("-1");
	else
		printf("%d", cost[xf][yf]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}