Cod sursa(job #2889204)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 12 aprilie 2022 14:06:35
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#import<fstream>

#import<vector>

#import<algorithm>

#import<cmath>

#import<queue>

#import<unordered_set>

#import<string>

using namespace std;

ifstream cin("car.in");

ofstream cout("car.out");

int rez[501][501][10];

const int dir=8,inf=2e9;

int dc[]={ 1, 1, 1, 0,-1,-1,-1, 0};

int dl[]={-1, 0, 1, 1, 1, 0,-1,-1};

int n,m;

bool inside(const int x,const int y)

{

    return (x>0 && x<=m && y>0 && y<=n);

}

bool ok[501][501];

struct idk

{

    int s,x,y,dir;

};

struct sortt

{

  bool operator()(idk a,idk b)

  {

      return a.s>=b.s;;

  }

};

main()

{

    int xi,xf,yi,yf;

    cin>>n>>m>>yi>>xi>>yf>>xf;

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            cin>>ok[j][i];

        }

    }

    for(int i=1;i<=n;i++)

    {

        for(int j=1;j<=m;j++)

        {

            for(int k=0;k<dir;k++)

            {

                rez[j][i][k]=inf;

            }

        }

    }

    priority_queue<idk,vector<idk>,sortt>q;

    for(int k=0;k<dir;k++)

    {

        rez[xi][yi][k]=0;

        q.push({0,xi,yi,k});

    }
    int maxx=2e9;

    while(!q.empty())

    {

        idk last=q.top();

        q.pop();
        if(rez[last.x][last.y][last.dir]>maxx)
        {
            break;
        }
        if(rez[last.x][last.y][last.dir]!=last.s)
        {

            continue;

        }
        for(int i=-2;i<=2;i++)

        {

            int directie=last.dir+i;

            if(directie<0)

            {

                directie+=8;

            }

            else if(directie>=8)

            {

                directie-=8;

            }

            int x=last.x+dc[directie];

            int y=last.y+dl[directie];

            if(!inside(x,y) || ok[x][y])

            {

                continue;

            }

            if(rez[x][y][directie]>last.s+abs(i))

            {

                rez[x][y][directie]=last.s+abs(i);
                if(x==xf && yf==y)
                {
                    maxx=0;
                    for(int j=0;j<8;j++)
                    {
                        maxx=max(rez[x][y][j],maxx);
                    }
                }
                else
                {
                    q.push({last.s+abs(i),x,y,directie});
                }


            }

        }

    }

    int minn=2e9;

    for(int k=0;k<dir;k++)

    {

        minn=min(minn,rez[xf][yf][k]);

    }

    if(minn!=2e9)

    {

        cout<<minn;

    }

    else cout<<-1;

}