Cod sursa(job #361880)

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

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

#define Nmax 550

const int dx[8]={-1,-1,-1,0,1,1,1,0}; 
const int dy[8]={-1,0,1,1,1,0,-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;
		 }
}

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]==0 && lne>=1 && lne<=n && cne>=1 && cne<=m)
			{
				if (cost[lne][cne]>cost[xx][yy]+move[d[xx][yy]][k])
				{
					cost[lne][cne]=cost[xx][yy]+move[d[xx][yy]][k];
					++u;
					qx[u]=lne;
					qy[u]=cne;
					d[lne][cne]=k;
				}
			}
		}
		p++;
	}
	
	
}


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

	for (i=1;i<=n;++i)
	{
		for (j=1;j<=m;++j)
			 printf("%d ", cost[i][j]);
		printf("\n");
	}
	

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