Cod sursa(job #593889)

Utilizator SpiderManSimoiu Robert SpiderMan Data 5 iunie 2011 10:19:20
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
# include <algorithm>
# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;

# define x first
# define y second

typedef pair <int, int> PR ;
const char *FIN = "car.in", *FOU = "car.out" ;
const int dx[] = { -1 , -1 , 0 , 1 , 1 ,  1 ,  0 , -1 } ;
const int dy[] = {  0 ,  1 , 1 , 1 , 0 , -1 , -1 , -1 } ;

queue <int> Q[2] ;
int D[9][513][513] ;
int V[501][501] ;
int N, M ;
PR I, F ;

int biti (int var, int bit) {
    return (var << bit) ;
}

int ls (int var, int bit) {
    return (var >> bit) ;
}

int main (void) {
    freopen (FIN, "r", stdin) ;

    scanf ("%d %d %d %d %d %d", &N, &M, &I.x, &I.y, &F.x, &F.y) ;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            scanf ("%d", V[i] + j) ;
        }
    }
    memset (D, 0x3f, sizeof (D)) ;
    for (int i = 0; i < 8; ++i) {
        Q[0].push (biti (I.x, 9) + biti (I.y, 0) + biti (i, 18)) ;
        D[i][I.x][I.y] = 0 ;
    }
    for (int l = 0; Q[0].size () + Q[1].size () > 0; ++l) {
        for (int ind = l & 1; !Q[ind].empty (); Q[ind].pop ()) {
            int P = Q[ind].front (), d = ls (P, 18);
            PR rec (ls (P, 9) & biti (1, 9) - 1, ls (P, 0) & biti (1, 9) - 1);
            if (rec == F) {
                fprintf (fopen (FOU, "w"), "%d", l) ;
                return 0 ;
            }
            PR act = rec ;
            act.x += dx[d], act.y += dy[d] ;
            if (act.x > 0 && act.y > 0 && act.x <= N && act.y <= M) {
                if (V[act.x][act.y] == 0 && D[d][act.x][act.y] > l) {
                    D[d][act.x][act.y] = l ;
                    Q[ind].push (biti (act.x, 9) + biti (act.y, 0) + biti (d, 18)) ;
                }
            }
            if (D[d + 1 & 7][rec.x][rec.y] > l + 1) {
                D[d + 1 & 7][rec.x][rec.y] = l + 1;
                Q[ind ^ 1].push (biti (rec.x, 9) + biti (rec.y, 0) + biti (d + 1 & 7, 18)) ;
            }
            if (D[d + 7 & 7][rec.x][rec.y] > l + 1) {
                D[d + 7 & 7][rec.x][rec.y] = l + 1;
                Q[ind ^ 1].push (biti (rec.x, 9) + biti (rec.y, 0) + biti (d + 7 & 7, 18)) ;
            }
        }
    }
    fprintf (fopen (FOU, "w"), "%d", -1) ;
}