Cod sursa(job #64592)

Utilizator sealTudose Vlad seal Data 4 iunie 2007 14:37:42
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include<stdio.h>
#define Nm 501
#define min(a,b) ((a)<(b)?(a):(b))
int M[Nm][Nm],Dm[1<<21],n,m,x0,y0,x1,y1,sol;
int Dx[]={-1,-1,0,1,1,1,0,-1},Dy[]={0,1,1,1,0,-1,-1,-1};
struct node
{
    int x;
    node *next;
} *L[Nm*Nm<<1];

void read()
{
    int i,j;

    freopen("car.in","r",stdin);
    scanf("%d%d%d%d%d%d",&n,&m,&x0,&y0,&x1,&y1);
    for(i=1;i<=n;++i)
	for(j=1;j<=m;++j)
	    scanf("%d",&M[i][j]);
}

void update(int x, int d)
{
    if(d<Dm[x])
    {
	node *q=new node;
	Dm[x]=d;
	q->x=x;
	q->next=L[d];
	L[d]=q;
    }
}

void solve()
{
    int i,j,x,y,d,nx,ny,nd;
    node *q;

    for(i=1;i<=n;++i)
	for(j=1;j<=m;++j)
	    for(d=0;d<8;++d)
		Dm[(i<<12)+(j<<3)+d]=n*m<<1;
    for(d=0;d<8;++d)
    {
	q=new node;
	x=(x0<<12)+(y0<<3)+d;
	Dm[x]=0;
	q->x=x;
	q->next=L[0];
	L[0]=q;
    }

    for(i=0;i<n*m<<1;++i)
	while(L[i])
	{
	    j=L[i]->x;
	    L[i]=L[i]->next;
	    if(Dm[j]<i)
		continue;
	    d=j&7;
	    y=j>>3&511;
	    x=j>>12;

	    nx=x+Dx[d];
	    ny=y+Dy[d];
	    if(nx && nx<=n && ny && ny<=m && !M[nx][ny])
		update((nx<<12)+(ny<<3)+d,Dm[j]);

	    nd=d+1;
	    if(nd>7)
		nd-=8;
	    nx=x+Dx[nd];
	    ny=y+Dy[nd];
	    if(nx && nx<=n && ny && ny<=m && !M[nx][ny])
		update((nx<<12)+(ny<<3)+nd,Dm[j]+1);

	    nd=d-1;
	    if(nd<0)
		nd+=8;
	    nx=x+Dx[nd];
	    ny=y+Dy[nd];
	    if(nx && nx<=n && ny && ny<=m && !M[nx][ny])
		update((nx<<12)+(ny<<3)+nd,Dm[j]+1);

	    nd=d+2;
	    if(nd>7)
		nd-=8;
	    nx=x+Dx[nd];
	    ny=y+Dy[nd];
	    if(nx && nx<=n && ny && ny<=m && !M[nx][ny])
		update((nx<<12)+(ny<<3)+nd,Dm[j]+2);

	    nd=d-2;
	    if(nd<0)
		nd+=8;
	    nx=x+Dx[nd];
	    ny=y+Dy[nd];
	    if(nx && nx<=n && ny && ny<=m && !M[nx][ny])
		update((nx<<12)+(ny<<3)+nd,Dm[j]+2);
	}

    sol=n*m<<1;
    for(d=0;d<8;++d)
	sol=min(sol,Dm[(x1<<12)+(y1<<3)+d]);
    if(sol==n*m<<1)
	sol=-1;
}

void write()
{
    freopen("car.out","w",stdout);
    printf("%d\n",sol);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}