Cod sursa(job #3342368)

Utilizator Dascalu_LucaDascalu Luca Petru Dascalu_Luca Data 23 februarie 2026 22:06:31
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");

const int INF=1e9;

struct Stare{
    int drum,directie;
    int linie,coloana;
};

struct ComparaCost {
    bool operator()(const Stare& a, const Stare& b) {
        return a.drum > b.drum; // Din nou, inversam pentru min-heap
    }
};

int N,M,Si,Sj,Fi,Fj,mat[505][505],d[505][505][8];
int curbe[5]={0,1,2,3,4};
int dir_i[8]={-1,-1,-1,0,1,1,1,0};
int dir_j[8]={-1,0,1,1,1,0,-1,-1};
priority_queue < Stare, vector<Stare>, ComparaCost > pq;

void citire(){
    fin>>N>>M>>Si>>Sj>>Fi>>Fj;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            fin>>mat[i][j];
        }
    }
    memset(d, 0x3f, sizeof(d));
}

void dijk(int start_i, int start_j){
    for(int i=0;i<8;i++){
        int lin=start_i+dir_i[i];
        int col=start_j+dir_j[i];
        if((lin>=1 && lin<=N && col>=1 && col<=M) && mat[lin][col]==0) {
            Stare nod;
            nod.drum=0;
            nod.linie=start_i;
            nod.coloana=start_j;
            nod.directie=i;
            d[start_i][start_j][i]=0;
            pq.push(nod);
        }
    }
    while(!pq.empty()){
        Stare x=pq.top();
        int dr=x.drum;
        int dir=x.directie;
        int i=x.linie,j=x.coloana;
        pq.pop();
        for(int k=0;k<8;k++){
            int lin=i+dir_i[k];
            int col=j+dir_j[k];
            if((lin>=1 && lin<=N && col>=1 && col<=M) && mat[lin][col]==0) {
                int next_dir=min(abs(dir-k),(8-abs(dir-k)));
                int next_cost=d[i][j][dir]+next_dir;
                if(next_cost<d[lin][col][k]){
                    d[lin][col][k]=next_cost;
                    Stare next;
                    next.drum=d[lin][col][k];
                    next.directie=k;
                    next.linie=lin;
                    next.coloana=col;
                    pq.push(next);
                }
            }
        }

    }
}

int main()
{
    citire();
    dijk(Si,Sj);
    int minim=INF ,minim_i;
    for(int i=0;i<8;i++){
        if(d[Fi][Fj][i]<minim){
            minim_i=i;
            minim=d[Fi][Fj][i];
        }
    }
    fout<<d[Fi][Fj][minim_i];
    return 0;
}