Cod sursa(job #2841655)

Utilizator proflaurianPanaete Adrian proflaurian Data 30 ianuarie 2022 10:14:10
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 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];
char used[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};
queue<tuple<int,int,int,int>> q;
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;
            else
                for(int k=0;k<8; k++)
                    used[k][i][j]=1;
        }
    for(int i=0;i<=n+1;i++)
    {
        for(int k=0;k<8;k++)
            used[k][i][0]=used[k][i][m+1]=1;
    }
    for(int j=0;j<=m+1;j++)
    {
        for(int k=0;k<8;k++)
            used[k][0][j]=used[k][n+1][j]=1;
    }

    for(int k=0;k<8;k++)
    {
        a[k][ip][jp]=0;
        q.push(make_tuple(0,k,ip,jp));
    }
    while(q.size())
    {
        int cst,dir,i,j;
        tie(cst,dir,i,j)=q.front();
        q.pop();
        if(used[dir][i][j]==1)
            continue;
        used[dir][i][j]=1;
        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(used[dir][I][J]==0)
            if(cst<a[dir][I][J])
            {
                a[dir][I][J]=cst;
                q.push(make_tuple(-cst,dir,I,J));
            }
        int DIR=rotL[dir];
        if(used[DIR][i][j]==0)
            if(cst+1<a[DIR][i][j])
            {
                a[DIR][i][j]=cst+1;
                q.push(make_tuple(-cst-1,DIR,i,j));
            }
        DIR=rotR[dir];
        if(!used[DIR][i][j])
            if(cst+1<a[DIR][i][j])
            {
                a[DIR][i][j]=cst+1;
                q.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;
}