Cod sursa(job #3315015)

Utilizator cutuslabutuNegrila Florin cutuslabutu Data 11 octombrie 2025 20:28:19
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
using namespace std;

int val(int cur, int next)
{
    int d = (next - cur + 8) % 8;
    return min(d, 8 - d);
}

int main()
{
    ifstream cin("car.in");
    ofstream cout("car.out");

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int N, M;
    cin >> N >> M;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    
    vector<vector<int>> grid(N + 2, vector<int>(M + 2, 1));
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            cin >> grid[i][j];

    if(grid[x1][y1] == 1 || grid[x2][y2] == 1)
    {
        cout << -1 << '\n';
        return 0;
    }

    vector<vector<vector<int>>> v(N + 2, vector<vector<int>>(M + 2, vector<int>(8, INT_MAX)));
    
    priority_queue<pair<int, pair<pair<int, int>, int>>, vector<pair<int, pair<pair<int, int>, int>>>, greater<pair<int, pair<pair<int, int>, int>>>> q;
    for (int i = 0; i < 8; ++i)
    {
        v[x1][y1][i] = 0;
        q.push({0, {{x1, y1}, i}});
    }

    while (!q.empty())
    {
        int cost = q.top().first;
        pair<int, int> cur = q.top().second.first;
        int dir = q.top().second.second;
        q.pop();
        
        if(cost > v[cur.first][cur.second][dir])
            continue;
        
        for (int i = 0; i < 8; ++i)
        {
            int ni = cur.first + dx[i];
            int nj = cur.second + dy[i];

            if (ni < 1 || ni > N || nj < 1 || nj > M)
                continue;

            if(grid[ni][nj] == 1)
                continue;

            int newVal = v[cur.first][cur.second][dir] + val(dir, i);

            if (newVal < v[ni][nj][i])
            {
                v[ni][nj][i] = newVal;
                q.push({newVal, {{ni, nj}, i}});
            }
        }
    }
    
    int result = INT_MAX;
    for(int i = 0; i < 8; ++i)
        result = min(result, v[x2][y2][i]);
    
    if(result == INT_MAX)
        cout << -1 << '\n';
    else
        cout << result << '\n';

    return 0;
}