Cod sursa(job #1726100)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 7 iulie 2016 12:35:39
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int nmax = 505;
const int INF = 2000000000;
int n,m,a[nmax][nmax],Si,Sj,Fi,Fj,ans;
int dp[nmax][nmax][10];
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

struct el
{
    int x,y,dir,cost;
};
queue < el > Q0,Q1;

inline bool OK(int i, int j)
{
    if(i < 1 || j < 1 || i > n || j > m || a[i][j]) return false;
    return true;
}


inline void Read()
{
    int i,j,k;
    el E;
    fin >> n >> m;
    fin >> Si >> Sj >> Fi >> Fj;
    for(i = 1; i <= n; i++)
        for(j = 1 ; j <= m; j++)
    {
        fin >> a[i][j];
        for(k = 0; k < 8 ;k++) dp[i][j][k] = INF;
    }
    for(k = 0; k < 8; k++)
    {
        E.x = Si, E.y = Sj;
        E.cost = 0;
        E.dir = k;
        Q0.push(E);
    }
}

inline void Dijkstra()
{
    int i,j,k;
    el E,W;
    while(!Q0.empty())
    {
        while(!Q0.empty())
        {
            E = Q0.front();
            Q0.pop();
            W.cost = E.cost, W.dir = E.dir;
            W.x = E.x + dx[E.dir];
            W.y  = E.y + dy[E.dir];
            if(OK(W.x,W.y) && dp[W.x][W.y][W.dir] > W.cost)
            {
                dp[W.x][W.y][W.dir] = W.cost;
                Q0.push(W);
            }
            W.cost++;
            W.dir = (E.dir + 1)%8;
            W.x = E.x;
            W.y  = E.y;
            if(OK(W.x,W.y) && dp[W.x][W.y][W.dir] > W.cost)
            {
                Q1.push(W);
                dp[W.x][W.y][W.dir] = W.cost;
            }
            W.dir = (E.dir -1);
            if(W.dir < 0) W.dir = 7;
            if(OK(W.x,W.y) && dp[W.x][W.y][W.dir] > W.cost)
            {
                Q1.push(W);
                dp[W.x][W.y][W.dir] = W.cost;
            }
        }
        while(!Q1.empty())
        {
            E = Q1.front();
            Q1.pop();
            Q0.push(E);
        }
    }

}

inline void Afisare()
{
    ans = dp[Fi][Fj][0];
    for(int i = 1; i < 8; i++) ans = min(ans,dp[Fi][Fj][i]);
    fout << (ans == INF? -1 : ans) << "\n";
    fout.close();
}
int main()
{
    Read();
    Dijkstra();
    Afisare();
    return 0;
}