Cod sursa(job #1295175)

Utilizator RaduVisanRadu Visan RaduVisan Data 18 decembrie 2014 22:04:01
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int NMAX = 510, INF = 0x3f3f3f3f;
const int DX[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int DY[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int N, M, StartX, StartY, EndX, EndY, A[NMAX][NMAX], Dist[NMAX][NMAX][8];

struct State
{
    int X, Y, D;
    State(int X, int Y, int D)
    {
        this -> X = X;
        this -> Y = Y;
        this -> D = D;
    }
};
queue<State> Q[2];

void Insert(int X, int Y, int D, int NextX, int NextY, int NextD, int QueueIndex, int Cost)
{
    if(!A[NextX][NextY] && Dist[X][Y][D] + Cost < Dist[NextX][NextY][NextD])
    {
        Dist[NextX][NextY][NextD] = Dist[X][Y][D] + Cost;
        Q[QueueIndex ^ Cost].push(State(NextX, NextY, NextD));
    }
}

void AddVec(State CrtState, int QueueIndex)
{
    int CrtX = CrtState.X, CrtY = CrtState.Y, CrtD = CrtState.D;
    Insert(CrtX, CrtY, CrtD, CrtX + DX[CrtD], CrtY + DY[CrtD], CrtD, QueueIndex, 0);
    Insert(CrtX, CrtY, CrtD, CrtX, CrtY, (CrtD + 1) % 8, QueueIndex, 1);
    Insert(CrtX, CrtY, CrtD, CrtX, CrtY, (CrtD + 7) % 8, QueueIndex, 1);
}

void Dijkstra()
{
    for(int i = 0; i <= M + 1; ++ i)
        A[0][i] = A[N + 1][i] = 1;
    for(int i = 0; i <= N + 1; ++ i)
        A[i][0] = A[i][M + 1] = 1;

    for(int i = 0; i < NMAX; ++ i)
        for(int j = 0; j < NMAX; ++ j)
            for(int k = 0; k < 8; ++ k)
                Dist[i][j][k] = INF;

    for(int i = 0; i < 8; ++ i)
        Dist[StartX][StartY][i] = 0,
        Q[0].push(State(StartX, StartY, i));

    int CurrentQueue = 0;
    while(!Q[CurrentQueue].empty())
    {
        while(!Q[CurrentQueue].empty())
        {
            State CurrentState = Q[CurrentQueue].front();
            Q[CurrentQueue].pop();
            if(CurrentState.X == EndX && CurrentState.Y == EndY)
            {
                printf("%i\n", Dist[EndX][EndY][CurrentState.D]);
                exit(0);
            }
            AddVec(CurrentState, CurrentQueue);
        }
        CurrentQueue ^= 1;
    }
}

int main()
{
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);

    scanf("%i %i %i %i %i %i", &N, &M, &StartX, &StartY, &EndX, &EndY);
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
            scanf("%i", &A[i][j]);

    Dijkstra();
    printf("-1\n");
}