Cod sursa(job #3357119)

Utilizator parus_majorParus Major parus_major Data 6 iunie 2026 15:00:06
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;

// Direcțiile: N, NE, E, SE, S, SV, V, NV
int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

struct State {
    int r, c, dir, cost;
    bool operator>(const State& other) const {
        return cost > other.cost;
    }
};

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

int main() {
    int N, M, Si, Sj, Fi, Fj;
    if (!(in >> N >> M)) return 0;
    in >> Si >> Sj >> Fi >> Fj;

    // Ajustare pentru indexare de la 0
    Si--; Sj--; Fi--; Fj--;

    vector<vector<int>> grid(N, vector<int>(M));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            in >> grid[i][j];

    // dist[linie][coloana][directie]
    vector<vector<vector<int>>> dist(N, vector<vector<int>>(M, vector<int>(8, INF)));
    priority_queue<State, vector<State>, greater<State>> pq;

    // Inițializare: din punctul de start se poate pleca în orice direcție cu cost 0
    for (int d = 0; d < 8; ++d) {
        int ni = Si + dr[d];
        int nj = Sj + dc[d];
        if (ni >= 0 && ni < N && nj >= 0 && nj < M && grid[ni][nj] == 0) {
            dist[ni][nj][d] = 0;
            pq.push({ ni, nj, d, 0 });
        }
    }

    int min_total_cost = INF;

    while (!pq.empty()) {
        State curr = pq.top();
        pq.pop();

        if (curr.cost > dist[curr.r][curr.c][curr.dir]) continue;
        if (curr.r == Fi && curr.c == Fj) {
            min_total_cost = min(min_total_cost, curr.cost);
            continue;
        }

        for (int d = 0; d < 8; ++d) {
            int ni = curr.r + dr[d];
            int nj = curr.c + dc[d];

            if (ni >= 0 && ni < N && nj >= 0 && nj < M && grid[ni][nj] == 0) {
                // Calculăm diferența de unghi (numărul de pași de 45 grade)
                int diff = abs(curr.dir - d);
                if (diff > 4) diff = 8 - diff; // Cea mai scurtă întoarcere

                int move_cost = diff;
                if (dist[ni][nj][d] > curr.cost + move_cost) {
                    dist[ni][nj][d] = curr.cost + move_cost;
                    pq.push({ ni, nj, d, dist[ni][nj][d] });
                }
            }
        }
    }

    if (Si == Fi && Sj == Fj) out << 0 << endl;
    else if (min_total_cost == INF) out << -1 << endl;
    else out << min_total_cost << endl;

    return 0;
}