Cod sursa(job #3167665)

Utilizator Giulian617Buzatu Giulian Giulian617 Data 10 noiembrie 2023 23:07:41
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
const int NMAX=505,INF=0x3F3F3F3F,DIRECTIONS=8;
const int dx[]= {-1,-1,-1,0,1,1,1,0};
const int dy[]= {-1,0,1,1,1,0,-1,-1};
int n,m,xs,ys,xf,yf,ans;
bitset<NMAX>a[NMAX],used[8][NMAX];
queue<tuple<int,int,int>>q[3];///because only operations 0,1 and 2 are relevant
vector<vector<vector<int>>>d;
inline bool check(int i,int j)
{
    if(i>=1 && i<=n && j>=1 && j<=m)
        return 1;
    return 0;
}
void dial()
{
    int x,y,direction,nx,ny,ndirection;
    int queue_no=0,no_elements=DIRECTIONS;///number of current queue, number of elements in all queues
    d.assign(DIRECTIONS,vector<vector<int>>(n+1,vector<int>(m+1,INF)));
    for(int i=0; i<DIRECTIONS; i++)
    {
        d[i][xs][ys]=0;
        q[0].push({i,xs,ys});
    }
    while(no_elements>0)
    {
        while(q[queue_no].empty())
            queue_no=(queue_no+1)%3;///MOD no_buckets
        tie(direction,x,y)=q[queue_no].front();///tie unpacks the tuple
        q[queue_no].pop();
        no_elements--;
        if(!used[direction][x][y])
        {
            for(int k=-2; k<0; k++) ///we check for 90 and 45 degrees to the left
            {
                ndirection=(direction+k+8)%DIRECTIONS;
                nx=x+dx[ndirection];
                ny=y+dy[ndirection];
                if(check(nx,ny) && !a[nx][ny] && !used[ndirection][nx][ny] && d[direction][x][y]-k<d[ndirection][nx][ny])
                {
                    d[ndirection][nx][ny]=d[direction][x][y]-k;
                    no_elements++;
                    q[(queue_no-k)%3].push({ndirection,nx,ny});///we add the cost to queue_no and because k is negative,
                    ///we do it by subtraction
                }
            }
            for(int k=0; k<3; k++) ///we check for 0,45 and 90 degrees to the right
            {
                ndirection=(direction+k)%DIRECTIONS;
                nx=x+dx[ndirection];
                ny=y+dy[ndirection];
                if(check(nx,ny) && !a[nx][ny] && !used[ndirection][nx][ny] && d[direction][x][y]+k<d[ndirection][nx][ny])
                {
                    d[ndirection][nx][ny]=d[direction][x][y]+k;
                    no_elements++;
                    q[(queue_no+k)%3].push({ndirection,nx,ny});///we add the cost to queue_no
                }
            }
            used[direction][x][y]=1;
        }
    }
}
int main()
{
    f>>n>>m>>xs>>ys>>xf>>yf;
    for(int i=1,x; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            f>>x;
            a[i][j]=x;
        }
    dial();
    ans=INF;
    for(int i=0; i<DIRECTIONS; i++)
        if(d[i][xf][yf]<ans)
            ans=d[i][xf][yf];
    if(ans==INF)
        g<<-1;
    else
        g<<ans;
    return 0;
}