Cod sursa(job #3357121)

Utilizator parus_majorParus Major parus_major Data 6 iunie 2026 15:03:01
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

const int INF = 1e9;

// Direcțiile de deplasare (8 direcții: N, NE, E, SE, S, SV, V, NV)
const int dl[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

struct State {
    int l, c, dir;
};

int N, M;
int Si, Sj, Fi, Fj;
int mat[505][505];
int dist[505][505][8];

// Funcție pentru a calcula costul schimbării de direcție
inline int get_cost(int old_dir, int new_dir) {
    int diff = abs(old_dir - new_dir);
    return min(diff, 8 - diff);
}

int main() {
    if (!fin) return 0;

    fin >> N >> M;
    fin >> Si >> Sj >> Fi >> Fj;

    // Indexăm de la 1 la N și 1 la M
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            fin >> mat[i][j];
            for (int d = 0; d < 8; ++d) {
                dist[i][j][d] = INF;
            }
        }
    }

    // Caz particular: startul este egal cu sosirea
    if (Si == Fi && Sj == Fj) {
        fout << 0 << "\n";
        return 0;
    }

    // Folosim 5 cozi pentru a procesa stările în ordinea costului crescător (Dial's Algorithm simplificat)
    queue<State> Q[5];
    int current_dist = 0;
    int states_in_queues = 0;

    // Din poziția inițială putem pleca în oricare dintre cele 8 direcții cu cost 0
    for (int d = 0; d < 8; ++d) {
        int nxt_l = Si + dl[d];
        int nxt_c = Sj + dc[d];

        if (nxt_l >= 1 && nxt_l <= N && nxt_c >= 1 && nxt_c <= M && mat[nxt_l][nxt_c] == 0) {
            dist[nxt_l][nxt_c][d] = 0;
            Q[0].push({ nxt_l, nxt_c, d });
            states_in_queues++;
        }
    }

    int min_total_cost = INF;

    // Parcurgerea algoritmului
    while (states_in_queues > 0) {
        int q_idx = current_dist % 5;

        while (!Q[q_idx].empty()) {
            State curr = Q[q_idx].front();
            Q[q_idx].pop();
            states_in_queues--;

            // Dacă am extras o stare cu o distanță mai mare decât cea deja optimizată, o ignorăm
            if (dist[curr.l][curr.c][curr.dir] < current_dist) {
                continue;
            }

            // Am ajuns la destinație? Actualizăm minimul global
            if (curr.l == Fi && curr.c == Fj) {
                min_total_cost = min(min_total_cost, current_dist);
            }

            // Încercăm să mergem în cele 8 direcții vecine
            for (int nxt_dir = 0; nxt_dir < 8; ++nxt_dir) {
                int nxt_l = curr.l + dl[nxt_dir];
                int nxt_c = curr.c + dc[nxt_dir];

                // Verificăm limitele matricii și dacă celula este liberă
                if (nxt_l >= 1 && nxt_l <= N && nxt_c >= 1 && nxt_c <= M && mat[nxt_l][nxt_c] == 0) {
                    int edge_cost = get_cost(curr.dir, nxt_dir);
                    int nxt_dist = current_dist + edge_cost;

                    if (nxt_dist < dist[nxt_l][nxt_c][nxt_dir]) {
                        dist[nxt_l][nxt_c][nxt_dir] = nxt_dist;
                        Q[nxt_dist % 5].push({ nxt_l, nxt_c, nxt_dir });
                        states_in_queues++;
                    }
                }
            }
        }
        current_dist++;
    }

    // Afișarea rezultatului
    if (min_total_cost == INF) {
        fout << -1 << "\n";
    } else {
        fout << min_total_cost << "\n";
    }

    return 0;
}