Cod sursa(job #203090)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 13 august 2008 17:10:23
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<stdio.h>
#include<string.h>
#define N 510
#define NMAX 2000010
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int car[NMAX],next[NMAX],a[N][N];
char s[8][N][N];
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]&(N+1);
			y=(car[pc]>>9)&(N+1);
			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]&(N+1);
			y=(car[i]>>9)&(N+1);
			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;
}