Cod sursa(job #203089)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 13 august 2008 17:07:41
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<stdio.h>
#include<string.h>
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int car[2000007],next[2000007],a[507][507];
char s[8][507][507];
int main(){
	int n,m,i,j,pc,qc,ql,x,y,xs,ys,xf,yf,dir,cost=0,e=0;
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%d%d%d%d",&xs,&ys,&xf,&yf);
	for(i=1;i<=n;++i)
		for(j=1;j<=m;++j)
			scanf("%d",&a[i][j]);
	for(i=0;i<=n+1;++i){      
        a[i][0]=1;
        a[i][m+1]=1;
	}
	for(j=0;j<=m+1;++j){      
        a[0][j]=1;
        a[n+1][j]=1;
	}
	for(i=0;i<8;++i){      
        car[i]=xs+(ys<<9)+(i<<18);
		s[i][xs][ys]=1;
	}
	pc=0;
	qc=7;
	ql=-1;
	while(1){
        while(qc>=pc){
            x=car[pc]&511;
			y=(car[pc]>>9)&511;
			if(x==xf&&y==yf){
                e=1;
                break;
			}
			dir=car[pc]>>18;
            if(!s[dir][x+dx[dir]][y+dy[dir]]&&!a[x+dx[dir]][y+dy[dir]]){
                car[++qc]=x+dx[dir]+((y+dy[dir])<<9)+(dir<<18);
                s[dir][x+dx[dir]][y+dy[dir]]=1;
            }
            pc++;
		}
		for(i=0;i<=qc;++i){      
            x=car[i]&511;
			y=(car[i]>>9)&511;
			dir=car[i]>>18;
            if(!s[(dir+1)&7][x][y]){      
                next[++ql]=x+(y<<9)+(((dir+1)&7)<<18);
				s[(dir+1)&7][x][y]=1;
			}
			dir--;
			if(dir<0)
				dir=7;
			if(!s[dir][x][y]){
				next[++ql]=x+(y<<9)+(dir<<18);
				s[dir][x][y] = 1;
			}
        }
		if(e)
			break;
		if(ql==-1){
			cost=-1;
			break;      
        }
        ++cost;
        memcpy(car,next,sizeof(car));
        pc=0;
		qc=ql;
		ql=-1;
	}
    printf("%d\n",cost);
	fclose(stdin);
	fclose(stdout);
	return 0;
}