Cod sursa(job #3254765)

Utilizator TonyyAntonie Danoiu Tonyy Data 8 noiembrie 2024 18:42:42
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <climits>
#define tuple tuple<int,int,int,int>
using namespace std;

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

const vector<int> dx({-1, -1, -1, 0, 0, 1, 1, 1});
const vector<int> dy({-1, 0, 1, -1, 1, -1, 0, 1});

int n, m, s1, s2, f1, f2;
const int Max = 501;
vector<vector<int>> a(Max, vector<int>(Max)), c(Max, vector<int>(Max, INT_MAX));
bitset<Max> v[Max];
priority_queue<tuple, vector<tuple>, greater<tuple>> q;

bool verify(int x, int y)
{
    return x >= 1 && y >= 1 && x <= n && y <= m && !a[x][y];
}

int calculate_cost(int d, int old_d)
{
    int cost = abs(d - old_d);
    return min(cost, 8 - cost);
}

int dijkstra(int x, int y)
{ 
    c[x][y] = 0;
    v[x][y] = 1;
    for(int d = 0; d < 8; ++d)
    {
        int new_x = x + dx[d];
        int new_y = y + dy[d];
        if(verify(new_x, new_y))
        {
            c[new_x][new_y] = 0;
            q.push({0, new_x, new_y, d});
        }
    }
    while(!q.empty())
    {
        auto [cost, x, y, old_d] = q.top();
        q.pop();
        if(v[x][y])
            continue;
        v[x][y] = 1;
        for(int d = 0; d < 8; ++d)
        {
            int new_x = x + dx[d];
            int new_y = y + dy[d];
            int cost = calculate_cost(d, old_d);
            if(verify(new_x, new_y) && c[x][y] + cost < c[new_x][new_y])
            {
                c[new_x][new_y] = c[x][y] + cost;
                q.push({c[new_x][new_y], new_x, new_y, d});
            }
        }
    }
    if(c[f1][f2] != INT_MAX)
        return c[f1][f2];
    return -1;
}

int main()
{
    fin >> n >> m >> s1 >> s2 >> f1 >> f2;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            fin >> a[i][j];
    fout << dijkstra(s1, s2);

    fin.close();
    fout.close();
    return 0;
}