Cod sursa(job #791717)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 septembrie 2012 22:43:15
Problema Car Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 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};

struct Vertex {
    int x, y, d;

    Vertex(int x, int y, int d) {
        this->x = x, this->y = y, this->d = d;
    }
};

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

void Initialize(const int &StartX, const int &StartY) {
    for (int D = 0; D < 8; ++D) {
        Dist[StartX][StartY][D] = 1;
        Q[0].push(Vertex(StartX, StartY, D));
    }
}

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

inline void Expand(const int &X, const int &Y, const int &D, const int &QI) {
    int NX, NY, ND;
    NX = X, NY = Y, ND = (D+7)%8;
    Update(X, Y, D, NX, NY, ND, QI, 1);
    NX = X, NY = Y, ND = (D+1)%8;
    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(const int &StartX, const int &StartY, const int &EndX, const int &EndY) {
    Initialize(StartX, StartY);
    for (int QI = 0; !Q[QI].empty() || !Q[QI^1].empty(); QI ^= 1) {
        for (; !Q[QI].empty(); Q[QI].pop()) {
            Vertex &V = Q[QI].front();
            int X = V.x, Y = V.y, D = V.d;
            if (X == EndX && Y == EndY) {
                SolDist = Dist[X][Y][D] - 1;
                return;
            }
            Expand(X, Y, D, QI);
        }
    }
}

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;
}