Cod sursa(job #791721)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 septembrie 2012 23:01:05
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <queue>
#include <cstring>
#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};
const int oo = 0x3f3f3f3f;

struct Vertex {
    int x, y, d;

    Vertex(const int x, const int y, const 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) {
    memset(Dist, oo, sizeof(Dist));
    for (int D = 0; D < 8; ++D) {
        Dist[StartX][StartY][D] = 0;
        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[X][Y][D]+C) {
        Dist[NX][NY][ND] = Dist[X][Y][D]+C;
        Q[QI^C].push(Vertex(NX, NY, ND));
    }
}

inline void Expand(const Vertex &V, const int &QI) {
    const int &X = V.x, &Y = V.y, &D = V.d;
    int NX, NY, ND;
    NX = X+DX[D], NY = Y+DY[D], ND = D;
    Update(X, Y, D, NX, NY, ND, QI, 0);
    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);
}

void Dijkstra(const int StartX, const int StartY, const int EndX, const int EndY) {
    Initialize(StartX, StartY);
    for (int QI = 0; !Q[QI].empty(); QI ^= 1) {
        for (; !Q[QI].empty(); Q[QI].pop()) {
            Vertex &V = Q[QI].front();
            if (V.x == EndX && V.y == EndY) {
                SolDist = Dist[V.x][V.y][V.d];
                return;
            }
            Expand(V, 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;
}