Cod sursa(job #162514)

Utilizator FlorinC1996Florin C FlorinC1996 Data 20 martie 2008 09:59:19
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 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;   
}