Cod sursa(job #217928)

Utilizator M@2Te4iMatei Misarca M@2Te4i Data 30 octombrie 2008 21:21:55
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <cstdio>
#include <cstring>

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[2000010],urm[2000010];
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++)
    {
        c[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=c[pc]&511;
            y=(c[pc]>>9)&511;
            if (x==xf && y==yf)
            {
                e=1;
                break;
            }
            dir=c[pc]>>18;
            if (!viz[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);
                viz[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 (!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(c, urm, sizeof(c));
        pc=0;
        qc=qu;
        qu=-1;
    }
    printf("%d\n", cost);
    return 0;
}