Cod sursa(job #282)

Utilizator testTest User test Data 8 decembrie 2006 17:05:32
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <stdio.h>
#include <stdlib.h>
const int MAX=504;
const int dx[8]={-1,-1,-1,0,1,1,1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
int m,n,i,j,k,ix,iy,sx,sy;
char d[MAX][MAX >> 3],used[(1<<21)>>3];             //3 biti pt dir, 9 biti pt i, 9 biti pt j
int x2,y2,dir2;
int current_cost;
long current_node;

class List                      //da da... stiu ca pot folosi STL, dar....
{
public:
    struct nod
    {
        long inf;
        nod *next;
    } *top;
    int nr;
    void inline add(int x,int y,int dir)
    {
        nod *aux=new nod;
        
        aux->inf = (dir<<18) + (x<<9) + y;
        aux->next=top;
        top=aux;
        nr++;
    }
    long inline pop()
    {
        long inf=top->inf;
        nod *aux=top->next;
        
        delete top;
        top=aux;
        nr--;
        return inf;
    }
} lst[2];

void inline move(long nod)
{
    int x,y,dir;
    dir = nod >> 18;
    x = (nod >> 9) & 511;
    y = nod & 511;
    used[nod >> 3] |= 1 << (nod & 7);

    if (x == sx && y == sy)
    {
        printf("%d\n", current_cost);
        exit(0);
    }

    for (i=dir-1; i<=dir+1; i+=2)
    {
        dir2 = i & 7;                    //i % 8 (fortat intotdeauna pozitiv)
        x2 = x + dx[dir2];
        y2 = y + dy[dir2];
        if ( x2 && y2 && x2<=n && y2<=n )
            lst[ ( current_cost + 1 ) & 1 ].add(x,y,dir2);
    }
    x2 = x + dx[dir];
    y2 = y + dy[dir];
    if (d[x2][y2 >> 3] & 1 << (y2 & 7))
        lst[ current_cost & 1 ].add(x2,y2,dir);
}

int main()
{
    freopen("car.in","rt",stdin);
    freopen("car.out","wt",stdout);
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &ix, &iy, &sx, &sy);
    
    for (i=0; i<2; i++) { lst[i].top = NULL; lst[i].nr = 0; }     //init() :P
    
    for (i=1; i<=n; i++)
        for (j=1; j<=m; j++)
        {
            scanf("%d", &k);
            if (k == 0)      
                d[i][j >> 3] |= 1 << (j & 7);                                       //inversez 0-urile si 1-urile, deoarece matricea e initial 0 si scap de bordare
        } 
            
    if ( ! ( d[ix][iy >> 3] & (1 << (iy & 7))) || ! ( d[sx][sy >> 3] & (1 << (sy & 7))) || n==0 || m==0 )
    {
        printf("-1\n");
        return 0;
    }
    
    for (i=0; i<8; i++) 
    {
        x2 = ix + dx[i];
        y2 = iy + dy[i];
        if (d[x2][y2 >> 3] & 1 << (y2 & 7))
             lst[0].add(x2, y2, i);
    }
    current_cost = 0;
    while (lst[0].nr + lst[1].nr > 0)
    {
        while (lst[current_cost & 1].nr > 0)
        {
            current_node = lst[current_cost & 1].pop();
            if ( ! (used[current_node >> 3] & (1 << (current_node & 7))) ) move ( current_node );
        }
        current_cost++;
    }
    printf("-1\n");
    return 0;
}