Cod sursa(job #791712)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 septembrie 2012 22:29:09
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <queue>
#include <cassert>

using namespace std;

const int MaxN = 505;
const int DX[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int DY[] = {0, 1, 1, 1, 0, -1, -1, -1};

int N, M, SX, SY, EX, EY, Map[MaxN][MaxN];
int Dist[MaxN][MaxN][8], SolDist;
queue<int> QX[2], QY[2], QD[2];

void Initialize(int StartX, int StartY) {
    for (int D = 0; D < 8; ++D) {
        Dist[StartX][StartY][D] = 1;
        QX[0].push(StartX), QY[0].push(StartY), QD[0].push(D);
    }
}

inline void Update(int X, int Y, int D, int NX, int NY, int ND, int QI, int C) {
    if (!Map[NX][NY] && !Dist[NX][NY][ND]) {
        Dist[NX][NY][ND] = Dist[X][Y][D]+C;
        QX[QI^C].push(NX), QY[QI^C].push(NY), QD[QI^C].push(ND);
    }
}

inline void Expand(int X, int Y, int D, int QI) {
    int NX, NY, ND;
    NX = X, NY = Y, ND = (D+7)&7;
    Update(X, Y, D, NX, NY, ND, QI, 1);
    NX = X, NY = Y, ND = (D+1)&7;
    Update(X, Y, D, NX, NY, ND, QI, 1);
    NX = X+DX[D], NY = Y+DY[D], ND = D;
    Update(X, Y, D, NX, NY, ND, QI, 0);
}

void Dijkstra(int StartX, int StartY, int EndX, int EndY) {
    Initialize(StartX, StartY);
    for (int QI = 0; !QX[QI].empty(); QI ^= 1) {
        for (; !QX[QI].empty(); QX[QI].pop(), QY[QI].pop(), QD[QI].pop()) {
            int X = QX[QI].front(), Y = QY[QI].front(), D = QD[QI].front();
            if (X == EndX && Y == EndY) {
                SolDist = Dist[X][Y][D] - 1;
                return;
            }
            Expand(X, Y, D, QI);
        }
    }
}

void Solve() {
    Dijkstra(SX, SY, EX, EY);
}

void Read() {
    assert(freopen("car.in", "r", stdin));
    assert(scanf("%d %d", &N, &M) == 2);
    assert(scanf("%d %d %d %d", &SX, &SY, &EX, &EY) == 4);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            assert(scanf("%d", &Map[i][j]) == 1);
    for (int i = 0; i <= N+1; ++i)
        Map[i][0] = Map[i][M+1] = 1;
    for (int j = 0; j <= M+1; ++j)
        Map[0][j] = Map[N+1][j] = 1;
}

void Print() {
    assert(freopen("car.out", "w", stdout));
    printf("%d\n", SolDist);
}

int main() {
    Read();
    SolDist = -1;
    Dijkstra(SX, SY, EX, EY);
    Print();
    return 0;
}