Cod sursa(job #2675765)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 22 noiembrie 2020 14:57:05
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <queue>
#include <climits>

using namespace std;

const int NMAX = 500;
const int MMAX = 500;

bool liber[2 + NMAX][2 + MMAX];
int cost[8][1 + NMAX][1 + MMAX];

int dx[] = {0,-1,-1,-1, 0, 1,1,1};
int dy[] = {1, 1, 0,-1,-1,-1,0,1};

priority_queue<pair<pair<int ,int>, pair<int, int>>, vector<pair<pair<int, int>, pair<int, int>>>, greater<pair<pair<int, int>, pair<int, int>>>> pq;

void dijkstra(int xs, int ys)
{
    pq.push(make_pair(make_pair(0, 0), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 1), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 2), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 3), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 4), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 5), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 6), make_pair(xs, ys)));
    pq.push(make_pair(make_pair(0, 7), make_pair(xs, ys)));

    while (!pq.empty())
    {
        int x = pq.top().second.first;
        int y = pq.top().second.second;

        int cost_ = pq.top().first.first;
        int dir = pq.top().first.second;

        pq.pop();

        if (cost_ > cost[dir][x][y]) continue;

        for (int i = 0; i < 8; i++)
        {
            int xVecin = x + dx[i];
            int yVecin = y + dy[i];

            if (liber[xVecin][yVecin])
            {
                int minim = abs(dir - i);
                if (minim > 4)
                {
                    minim = 8 - minim;
                }

                if (cost_ + minim < cost[i][xVecin][yVecin])
                {
                    cost[i][xVecin][yVecin] = cost_ + minim;
                    pq.push(make_pair(make_pair(cost_ + minim, i), make_pair(xVecin, yVecin)));
                }
            }
        }
    }
}

int main()
{
    ifstream in("car.in");
    ofstream out("car.out");
    int n, m;
    int xs, ys, xf, yf;

    in >> n >> m;
    in >> xs >> ys >> xf >> yf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            in >> liber[i][j];
            liber[i][j] = !liber[i][j];
            for (int k = 0; k < 8; k++)
            {
                cost[k][i][j] = INT_MAX;
            }
        }
    }

    for (int i = 0; i < 8; i++)
    {
        cost[i][xs][ys] = 0;
    }

    dijkstra(xs, ys);

    int minim = cost[0][xf][yf];
    for (int i = 1; i < 8; i++)
    {
        if (cost[i][xf][yf] < minim)
        {
            minim = cost[i][xf][yf];
        }
    }

    out << minim << '\n';

    return 0;
}