Cod sursa(job #2841652)

Utilizator proflaurianPanaete Adrian proflaurian Data 30 ianuarie 2022 09:53:26
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("car.in");
ofstream g("car.out");
const int oo = 1<<30;
int n,m,ip,jp,is,js,a[8][502][502];
int depI[8]={-1,-1,0,1,1, 1, 0,-1};
int depJ[8]={ 0, 1,1,1,0,-1,-1,-1};
int rotL[8]={7,0,1,2,3,4,5,6};
int rotR[8]={1,2,3,4,5,6,7,0};
priority_queue<tuple<int,int,int,int>> pq;
int main()
{
    f>>n>>m>>ip>>jp>>is>>js;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            int x;
            f>>x;
            if(x==0)
                for(int k=0; k<=8; k++)
                    a[k][i][j]=oo;
        }
    for(int k=0;k<8;k++)
    {
        a[k][ip][jp]=0;
        pq.push(make_tuple(0,k,ip,jp));
    }
    while(pq.size())
    {
        int cst,dir,i,j;
        tie(cst,dir,i,j)=pq.top();
        pq.pop();
        cst=-cst;
        /// sunt intr-o anumita pozitie pozitionat pe o anumita directie si am ajuns acolo cu un anumit cost
        /// aseasta stare are cel mai mic cost disponibil
        /// din aceasta pozitie am 3 optiuni
            ///-> avansez fara sa fac curba => am acelasi cost
            ///-> fac 45 grade dreapta => cresc costul cu 1
            ///-> fac 45 grade stanga => cresc costul cu 1
        /// ajung intr-o noua stare pe care o iau in considerare doar daca imi imbunatateste costul
        /// VARIANTA 1 -> ma misc
        int I=i+depI[dir];
        int J=j+depJ[dir];
        if(cst<a[dir][I][J])
        {
            a[dir][I][J]=cst;
            pq.push(make_tuple(-cst,dir,I,J));
        }
        int DIR=rotL[dir];
        if(cst+1<a[DIR][i][j])
        {
            a[DIR][i][j]=cst+1;
            pq.push(make_tuple(-cst-1,DIR,i,j));
        }
        DIR=rotR[dir];
        if(cst+1<a[DIR][i][j])
        {
            a[DIR][i][j]=cst+1;
            pq.push(make_tuple(-cst-1,DIR,i,j));
        }
    }
    int sol=a[0][is][js];
    for(int k=1;k<8;k++)
        sol=min(sol,a[k][is][js]);
    g<<sol;
    return 0;
}