Cod sursa(job #203698)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 18 august 2008 17:31:27
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
#define N 507
#define M 8
#define D 7
#define Y 4090
#define X 2093060
int v[N][N],min[M][N][N],car[N*N*M];
int sx,sy,fx,fy,q,sf,s=0;
int dir[M][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
void add(int sx,int sy,int d,int ct){
	int i,j;
	for(i=sx,j=sy;!v[i][j];i+=dir[d][0],j+=dir[d][1])
		if(!min[d][i][j]){
			min[d][i][j]=ct;
			car[++sf]=(((i<<9)+j)<<3)+d;
			if((i==fx)&&(j==fy))
				s=ct;
		}
}
int main (){
	int i,j,d,n,m;
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
	for(i=0;i<=n+1;++i)
		for(j=0;j<=m+1;++j)
			v[i][j]=1;
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&v[i][j]);
	for(sf=-1,i=0;i<M;++i)
		add(sx,sy,i,1);
	for(q=0;(q<=sf)&&(!s);++q){
		i=car[q]>>12;
		j=(car[q]&Y)>>3;
		d=car[q]&D;
		add(i,j,(d+1)%M,min[d][i][j]+1);
		add(i,j,(d+M-1)%M,min[d][i][j]+1);
	}
	s--;
	printf("%d\n",s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}