Cod sursa(job #2887474)

Utilizator NutaAlexandruASN49K NutaAlexandru Data 9 aprilie 2022 18:27:45
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 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});
    }
    while(!q.empty())
    {
        idk last=q.top();
        q.pop();
        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);
                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(!rez[xf][yf][k])
        {
            cout<<k;
        }
    }
    cout<<minn;
}