Cod sursa(job #2416094)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 26 aprilie 2019 21:42:42
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <fstream>
#include <queue>
#include <vector>
#include <utility>

#define pp pair<int, int>

using namespace std;

ifstream fin("car.in");
ofstream fout("car.out");

const int NMax = 500, oo = 2e9;

int A[8][8]= {{0, 1, 2, 3, 4, 3, 2, 1},
              {1, 0, 1, 2, 3, 4, 3, 2},
              {2, 1, 0, 1, 2, 3, 4, 3},
              {3, 2, 1, 0, 1, 2, 3, 4},
              {4, 3, 2, 1, 0, 1, 2, 3},
              {3, 4, 3, 2, 1, 0, 1, 2},
              {2, 3, 4, 3, 2, 1, 0, 1},
              {1, 2, 3, 4, 3, 2, 1, 0}};

int dl[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, dc[8] = {0, 1, 1, 1, 0, -1, -1, -1}, N, M, l1, c1, l2, c2;

int DP[NMax + 5][NMax + 5][8], V[NMax + 5][NMax + 5], Use[NMax + 5][NMax + 5][8], C[NMax + 5][NMax + 5][8], K;

struct cell{int l, c, o;};

vector <cell> S; priority_queue <pp, vector<pp>, greater<pp>> Q;

inline bool valid(int i, int j) { return i && j && i <= N && j <= M && V[i][j] == 0;}

void Dijkstra()
{
    int Nod, l, c, o, nl, nc, cost;

    for(int i = 0; i < 8; i++)
    {
        nl = l1 + dl[i], nc = c1 + dc[i], DP[l1][c1][i] = 0;
        if(!valid(nl, nc)) continue;

        DP[nl][nc][i] = 0, Q.push({0, C[nl][nc][i]});
    }
    while(Q.size())
    {
        Nod = Q.top().second, l = S[Nod].l, c = S[Nod].c, o = S[Nod].o; Q.pop();
        if(Use[l][c][o]) continue;

        for(int i = 0; i < 8; i++)
        {
            nl = l + dl[i], nc = c + dc[i], cost = DP[l][c][o] + A[o][i];

            if(valid(nl, nc) && DP[nl][nc][i] > cost)
            {
                DP[nl][nc][i] = cost;
                Q.push({cost, C[nl][nc][i]});
            }
        }
        Use[l][c][o] = 1;
    }
}

int main()
{
    fin >> N >> M >> l1 >> c1 >> l2 >> c2;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
        {
            fin >> V[i][j];

            for(int k = 0; k < 8; k++)
                DP[i][j][k] = oo, C[i][j][k] = K++, S.push_back({i, j, k});
        }
    Dijkstra(); int Sol = oo;

    for(int i = 0; i < 8; i++)
        Sol = min(Sol, DP[l2][c2][i]);

    fout << Sol << '\n';

    fin.close();
    fout.close();

    return 0;
}