Cod sursa(job #179772)

Utilizator razvi9Jurca Razvan razvi9 Data 16 aprilie 2008 12:33:23
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<cstdio>
#include<cstring>
#include<deque>
int n,m,xb,yb,xf,yf,a[501][501],i,j,st,dr,d,curba[9][9],cost,ok,st1,dr1;
const int inf=0x7f7f7f7f;
const int dy[9]={0,0,-1,-1,-1,0,1,1,1};
const int dx[9]={0,1,1,0,-1,-1,-1,0,1};
const int next[9]={0,2,3,4,5,6,7,8,1};
const int prev[9]={0,8,1,2,3,4,5,6,7};
int viz[501][501][9];
struct list{int i,j,d;};
list l[/*500*500*8*/100];
int go(int x,int y,int d)
{
	x+=dx[d];y+=dy[d];
	if(x<1 || y<1 || x>n || y>m) return 0;
	if(a[x][y]) return 0;
	if(viz[x][y][d]) return 0;
	viz[x][y][d]=1;
	++dr;
	l[dr].i=x;
	l[dr].j=y;
	l[dr].d=d;
	return 1;
}
int go2(int x,int y,int d)
{
	d=next[d];
	if(viz[x][y][d]) return 0;
	viz[x][y][d]=1;
	++dr;
	l[dr].i=x;
	l[dr].j=y;
	l[dr].d=d;
	return 1;
}
int go3(int x,int y,int d)
{
	d=prev[d];
	if(viz[x][y][d]) return 0;
	viz[x][y][d]=1;
	++dr;
	l[dr].i=x;
	l[dr].j=y;
	l[dr].d=d;
	return 1;
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d %d",&n,&m);
	scanf("%d %d",&i,&j);xb=i;yb=j;
	scanf("%d %d",&i,&j);xf=i;yf=j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	st=0;dr=-1;cost=0;
	for(i=1;i<=8;i++){++dr;l[dr].i=xb;l[dr].j=yb;l[dr].d=i;}
	while(1)
	{
		ok=0;
		st1=st;
		while(st1<=dr)
		{
			i=l[st1].i;
			j=l[st1].j;
			if(i==xf && j==yf) goto end;
			d=l[st1].d;
			if(go(i,j,d)) ok=1;
			st1++;
		}
		dr1=dr;
		while(st<=dr1)
		{
			i=l[st].i;
			j=l[st].j;
			d=l[st].d;
			if(go2(i,j,d)) ok=1;
			if(go3(i,j,d)) ok=1;
			st++;
		}
		cost++;
		if(!ok)break;
	}
	cost=-1;
end:
	printf("%d",cost);
	fclose(stdout);
	return 0;
}