Cod sursa(job #373000)

Utilizator DraStiKDragos Oprica DraStiK Data 12 decembrie 2009 13:25:58
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <algorithm>
using namespace std;

#define DIM 505
#define MAX 8

int dx[MAX]={-1,-1,0,1,1, 1, 0,-1};
int dy[MAX]={ 0, 1,1,1,0,-1,-1,-1};
int viz[MAX][DIM][DIM];
int a[DIM][DIM],q[2][DIM*DIM*MAX];
int n,m,xi,yi,xf,yf,cost,st1,dr1;

void read ()
{
    int i,j;

    scanf ("%d%d%d%d%d%d",&n,&m,&xi,&yi,&xf,&yf);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
            scanf ("%d",&a[i][j]);
}

void init ()
{
    int i;

    for (i=0; i<MAX; ++i)
    {
        q[0][++dr1]=(i<<18)+(yi<<9)+xi;
        viz[i][xi][yi]=1;
    }
}

int valid (int x,int y)
{
    if (x<=0 || y<=0 || x>n || y>m)
        return 0;
    return 1;
}

void solve ()
{
    int t1,t2,st2,dr2,ok,dir,dir1,x,y;

    for (dr2=t1=0, t2=1, ok=0; !ok; )
    {
        for (st1=1; st1<=dr1; ++st1)
        {
            dir=q[t1][st1]>>18;
            x=q[t1][st1]&511;
            y=(q[t1][st1]>>9)&511;
            if (x==xf && y==yf)
                ok=1;
            else if (valid (x+dx[dir],y+dy[dir]) && !a[x+dx[dir]][y+dy[dir]] && !viz[dir][x+dx[dir]][y+dy[dir]])
            {
                q[t1][++dr1]=x+dx[dir]+((y+dy[dir])<<9)+(dir<<18);
                viz[dir][x+dx[dir]][y+dy[dir]]=1;
            }
        }
        for (st2=1; st2<=dr1; ++st2)
        {
            dir=q[t1][st2]>>18;
            x=q[t1][st2]&511;
            y=(q[t1][st2]>>9)&511;
            dir1=(dir+1)&7;
            if (!viz[dir1][x][y])
            {
                viz[dir1][x][y]=1;
                q[t2][++dr2]=x+(y<<9)+(dir1<<18);
            }
            dir1=dir-1;
            if (dir1<0)
                dir1=7;
            if (!viz[dir1][x][y])
            {
                viz[dir1][x][y]=1;
                q[t2][++dr2]=x+(y<<9)+(dir1<<18);
            }
        }
        if (!ok && !dr2)
        {
            printf ("-1");
            return ;
        }
        if (!ok)
            ++cost;
        t1^=t2^=t1^=t2;
        dr1=dr2;
        dr2=0;
    }
    printf ("%d",cost);
}

int main ()
{
    freopen ("car.in","r",stdin);
    freopen ("car.out","w",stdout);

    read ();
    init ();
    solve ();

    return 0;
}