Cod sursa(job #3255656)

Utilizator TonyyAntonie Danoiu Tonyy Data 11 noiembrie 2024 18:19:27
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <bits/stdc++.h>
#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, ans = INT_MAX;
const int Max = 501;
vector<vector<int>> a(Max, vector<int>(Max));
vector<vector<vector<int>>> c(8, vector<vector<int>>(Max, vector<int>(Max, INT_MAX)));
bitset<Max> v[8][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)
{
    if(old_d == d)
        return 0;

    if(old_d > 4) 
        old_d -= 5;
    else if(old_d > 2) 
        old_d = 1;

    if(d > 4) 
        d -= 5;
    else if(d > 2) 
        d = 1;

    if(old_d == d)
        return 2;

    return abs(d - old_d);
}

void dijkstra(int x, int y, int D)
{ 
    while(!q.empty())
    {
        x = get<1>(q.top());
        y = get<2>(q.top());
        int old_d = get<3>(q.top());
        q.pop();
        if(v[D][x][y])
            continue;
        v[D][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[D][x][y] + cost < c[D][new_x][new_y])
            {
                c[D][new_x][new_y] = c[D][x][y] + cost;
                q.push({c[D][new_x][new_y], new_x, new_y, d});
            }
        }
    }
}

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];
    
    for(int d = 0; d < 8; ++d)
    {
        int new_x = s1 + dx[d];
        int new_y = s2 + dy[d];
        if(verify(new_x, new_y))
        {
            v[d][s1][s2] = 1;
            c[d][s1][s2] = 0;
            c[d][new_x][new_y] = 0;
            q.push({0, new_x, new_y, d});
            dijkstra(new_x, new_y, d);
        }
        ans = min(ans, c[d][f1][f2]);
    }
    if(ans != INT_MAX)
        fout << ans;
    else
        fout << -1;

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