Cod sursa(job #191726)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 28 mai 2008 08:10:37
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<stdio.h> 
#include<string.h>
#define N 2000005
int n,m,a[510][510];
int dx[]={-1,-1,0,1,1,1,0,-1};      
int dy[]={0,1,1,1,0,-1,-1,-1};
int c[N];
int u[N];
char v[8][510][510];
int main(){
    int i,j,pc,qc,pu,qu,x,y,x1,y1,x2,y2,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",&x1,&y1,&x2,&y2);
    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++){
		c[i]=x1+(y1<<9)+(i<<18);
		v[i][x1][y1]=1;
	}
	pc=0;
	qc=7;
    pu=0;
    qu=-1;
	while(1){
        while(pc<=qc){  
            x=c[pc]&511;      
            y=(c[pc]>>9)&511;
            if(x==x1&&y==y2){
                e=1;
				break;
            }
            dir=c[pc]>>18;
            if(!v[dir][x+dx[dir]][y+dy[dir]]&&!a[x+dx[dir]][y+dy[dir]]){
                c[++qc]=x+dx[dir]+((y+dy[dir])<<9)+(dir<<18);
				v[dir][x+dx[dir]][y+dy[dir]]=1;
			}
			pc++;
		}
		for(i=0;i<=qc;i++){
			x=c[i]&511;
			y=(c[i]>>9)&511;
			dir=c[i]>>18;            
			if(!v[(dir+1)&7][x][y]){
                u[++qu]=x+(y<<9)+(((dir+1)&7)<<18);
				v[(dir+1)&7][x][y]=1;
			}
            dir--;      
            if(dir<0)
				dir=7;
            if(!v[dir][x][y]){
				u[++qu]=x+(y<<9)+(dir<<18);
				v[dir][x][y]=1;
			}
		}
        if(e)
			break;      
        if(qu==-1){
			cost=-1;
			break;      
        }
        cost ++;
        memcpy(c, u, sizeof(c));
		pc=0;
		qc=qu;
		qu=-1;
	}
    printf("%d\n", cost);
	fclose(stdin);
	fclose(stdout);
	return 0;
}