Cod sursa(job #191730)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 28 mai 2008 08:15:25
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<stdio.h>
#include<string.h>
#define N 2000010
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 cur[N],urm[N];
char viz[8][510][510];
int main(){
    int i,j,pc,qc,pu,qu,x,y,xb,yb,xf,yf,dir;
    freopen("car.in","r",stdin);
    freopen("car.out","w",stdout);
    scanf("%d %d",&n,&m);
    scanf("%d %d %d %d",&xb,&yb,&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++){
		cur[i]=xb+(yb<<9)+(i<<18);
		viz[i][xb][yb]=1;
	}
	pc=0;
	qc=7;
    pu=0;
    qu=-1;
	int cost=0;      
    int e=0;
	while(1){
        while(pc<=qc){  
            x=cur[pc]&511;      
            y=(cur[pc]>>9)&511;
            if(x==xf&&y==yf){
                e=1;
				break;
            }
            dir=cur[pc]>>18;
            if(!viz[dir][x+dx[dir]][y+dy[dir]]&&!a[x+dx[dir]][y+dy[dir]]){
                cur[++qc]=x+dx[dir]+((y+dy[dir])<<9)+(dir<<18);
				viz[dir][x+dx[dir]][y+dy[dir]]=1;
			}
			pc++;
		}
		for(i=0;i<=qc;i++){
			x=cur[i]&511;
			y=(cur[i]>>9)&511;
			dir=cur[i]>>18;            
			if(!viz[(dir+1)&7][x][y]){
                urm[++qu]=x+(y<<9)+(((dir+1)&7)<<18);
				viz[(dir+1)&7][x][y]=1;
			}
            dir--;      
            if(dir<0)
				dir=7;
            if(!viz[dir][x][y]){
				urm[++qu]=x+(y<<9)+(dir<<18);
				viz[dir][x][y]=1;
			}
		}
        if(e)
			break;      
        if(qu==-1){
			cost=-1;
			break;      
        }
        cost ++;
        memcpy(cur, urm, sizeof(cur));
		pc=0;
		qc=qu;
		qu=-1;
	}
    printf("%d\n", cost);
	fclose(stdin);
	fclose(stdout);
	return 0;
}