Cod sursa(job #1003997)

Utilizator poptibiPop Tiberiu poptibi Data 1 octombrie 2013 21:31:17
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

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

struct State
{
    int X, Y, Dir;
    State(int X, int Y, int Dir)
    {
        this -> X = X;
        this -> Y = Y;
        this -> Dir = Dir;
    }
};
 
int N, M, StartX, StartY, EndX, EndY, Mat[NMAX][NMAX], Dist[NMAX][NMAX][8], Ans;
queue<State> Q[2];
 
void Update(int X, int Y, int Dir, int NewX, int NewY, int NewDir, int QIndex, int Change)
{
    if(!Mat[NewX][NewY] && Dist[NewX][NewY][NewDir] > Dist[X][Y][Dir] + Change)
    {
        Dist[NewX][NewY][NewDir] = Dist[X][Y][Dir] + Change;
        Q[QIndex ^ Change].push(State(NewX, NewY, NewDir));
    }
}
 
void Expand(State Now, int QIndex)
{
    int X = Now.X, Y = Now.Y, Dir = Now.Dir;
    Update(X, Y, Dir, X + DX[Dir], Y + DY[Dir], Dir, QIndex, 0);
    Update(X, Y, Dir, X, Y, (Dir + 7) % 8, QIndex, 1);
    Update(X, Y, Dir, X, Y, (Dir + 1) % 8, QIndex, 1);
}

void Dijkstra()
{
    memset(Dist, INF, sizeof(Dist));
    for(int Dir = 0; Dir < 8; Dir ++)
    {
        Dist[StartX][StartY][Dir] = 0;
        Q[0].push(State(StartX, StartY, Dir));
    }
    
    for(int QIndex = 0; !Q[QIndex].empty(); QIndex = 1 - QIndex)
    {
        while(!Q[QIndex].empty())
        {
            State Now = Q[QIndex].front();
            Q[QIndex].pop();
            if(Now.X == EndX && Now.Y == EndY)
            {
                printf("%i\n", Dist[Now.X][Now.Y][Now.Dir]);
                exit(0);
            }
            Expand(Now, QIndex);
        }
    }
}

int main()
{
    freopen("car.in", "r", stdin);
    freopen("car.out", "w", stdout);
    
    scanf("%i %i", &N, &M);
    scanf("%i %i %i %i", &StartX, &StartY, &EndX, &EndY);
    for(int i = 1; i <= N; ++ i)
        for(int j = 1; j <= M; ++ j)
            scanf("%i", &Mat[i][j]);
    for(int i = 0; i <= N + 1; ++ i)
        Mat[i][0] = Mat[i][M + 1] = 1;
    for(int i = 0; i <= M + 1; ++ i)
        Mat[0][i] = Mat[N + 1][i] = 1;
    
    Dijkstra();
    printf("-1\n");
    return 0;
}