Cod sursa(job #129155)

Utilizator pishtymatei silviu pishty Data 28 ianuarie 2008 18:15:45
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <stdio.h>     
#include <string.h>     
     
int n, m;     
     
int 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[2000010];     
int 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++)     
    {     
        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)     
    {     
        //expandez cur pana nu mai pot     
     
        while (pc <= qc)     
        {     
            x = cur[pc] & 511;     
            y = (cur[pc] >> 9) & 511;     
     
            if (x == xf && y == yf)     
            {     
                e = 1;     
                break;     
            }     
            dir = cur[pc] >> 18;     
                 
            // acu mut una in directie     
     
            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;     
     
            // il mut cu o directie in plus     
            if (!viz[(dir + 1) & 7][x][y])     
            {     
                urm[++qu] = x + (y << 9) + (((dir + 1) & 7) << 18);     
                viz[(dir + 1) & 7][x][y] = 1;     
            }     
     
            //il mut cu o directie in minus     
            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;     
}