Cod sursa(job #3360192)

Utilizator nicoleta_iancuIancu Nicoleta nicoleta_iancu Data 10 iulie 2026 01:54:11
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.76 kb
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
#define inf 1e9
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMAX=501;
bool mat[NMAX][NMAX];
vector<pair<int,int>>direction={{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1}};//transformam indexul directiei in (?cum se misca in matrice ?) 
//prima e pt i si a doua j
int n,m;
int iStart,jStart,iEnd,jEnd;
struct stare{
    int i,j;//poxitia curenta
    short directie;//numerotam fiecare directie de la 1, la 7 
    /*(steluta ,wow)
      \ 3|2/1
    4___\|/___0
        /|\
      5/ | \7
          6*/   
    int cost;//costul ca sa ajungem in starea curenta daca pornim de la (1,1)
    bool operator<(const stare& other) const{
        return cost>other.cost;
    };
    stare(int x,int y,int d,int c):i(x),j(y),directie(d),cost(c){};
};
int dist[NMAX][NMAX][8];//dist[i][j][d]= costul minim ca sa ajunga de la (0,0) la (i,j) cu directia d
void Disjakstra(){
    deque<stare>pq;
    for(int i=0;i<8;++i){ 
        dist[iStart][jStart][i]=0;
        pq.push_back(stare(iStart,jStart,i,0));
    }
    while (!pq.empty())
    {
        stare crt=pq.front();
        pq.pop_front();
        int dir1=(crt.directie+1)%8;
        int dir2=(crt.directie-1+8)%8;
        
        int costCrt=crt.cost+1;
        if(dist[crt.i][crt.j][dir1]>costCrt){
            dist[crt.i][crt.j][dir1]=costCrt;
            stare newStare=crt;
            newStare.directie=dir1;
            newStare.cost=costCrt;
            pq.push_back(newStare);
        }
        if(dist[crt.i][crt.j][dir2]>costCrt){
            dist[crt.i][crt.j][dir2]=costCrt;
            stare newStare=crt;
            newStare.directie=dir2;
            newStare.cost=costCrt;
            pq.push_back(newStare);
        }
        int dir=crt.directie;
        int newi=crt.i+direction[dir].first;
        int newj=crt.j+direction[dir].second;
        if(newi>=0 && newi<n && newj>=0 && newj<m && mat[newi][newj]==0 && mat[newi][newj]==0 && crt.cost<dist[newi][newj][dir]){
            dist[newi][newj][dir]=crt.cost;
            stare newStare=stare(newi,newj,crt.directie,crt.cost);
            pq.push_front(newStare);
        }
    }
    
}
int getAnswer(){
    int rez=inf;
    for(int i=0;i<8;++i){
        rez=min(rez,dist[iEnd][jEnd][i]);
    }
    return rez;
}
void setup(){
    for(int i=0;i<NMAX;++i){
        for(int j=0;j<NMAX;++j){
            for(int k=0;k<8;++k){
                dist[i][j][k]=inf;
            }
        }
    }
}
void read(){
    fin>>n>>m;
    fin>>iStart>>jStart>>iEnd>>jEnd;
    iStart--;
    jStart--;
    iEnd--;
    jEnd--;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            fin>>mat[i][j];
        }
    }
}
int main(){

    setup();
    read();
    Disjakstra();
    fout<<getAnswer();
    return 0;
}