Cod sursa(job #2635027)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 12 iulie 2020 23:42:31
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <bitset>
using namespace std;
ifstream in ("car.in");
ofstream out("car.out");
struct state
{
    int x, y, d;
};
deque <int> q;

///0->7 clockwise
int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[]={0, 1, 1, 1, 0, -1, -1, -1};
bitset <503> barrier[503];
int dp[503][503][8], xi, yi, xf, yf;
inline int toCode(state p)
{
    return (p.x * 512 + p.y) * 8 + p.d;
}
inline state fromCode(int p)
{
    state rez;


    rez.d=p%8;
    rez.y=((p-rez.d)/8)%512;
    rez.x=((p-rez.d)/8-rez.y)/512;
    return rez;
}
int n, m, val;
int main()
{
    in>>n>>m>>xi>>yi>>xf>>yf;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            in>>val;
            barrier[i][j]=val;
            for(int t=0; t<8; t++)
                dp[i][j][t]=2e9;
        }
    for(int i=0; i<=n+1; i++) barrier[i][0]=barrier[i][m+1]=1;
    for(int i=0; i<=m+1; i++) barrier[0][i]=barrier[n+1][i]=1;
    for(int i=0; i<8; i++)
        q.push_back(toCode({xi, yi, i})), dp[xi][yi][i]=0;

    while(!q.empty())
    {
        state s=fromCode(q.front());
        q.pop_front();
        if(s.x==xf&&s.y==yf)
        {
            out<<dp[s.x][s.y][s.d];
            return 0;
        }

        if(dp[s.x][s.y][(s.d+1)%8]>dp[s.x][s.y][s.d]+1)
        {
            dp[s.x][s.y][(s.d+1)%8]=dp[s.x][s.y][s.d]+1;
            q.push_back(toCode({s.x, s.y, (s.d+1)%8}));
        }

        if(dp[s.x][s.y][(s.d+7)&7]>dp[s.x][s.y][s.d]+1)
        {
            dp[s.x][s.y][(s.d+7)&7]=dp[s.x][s.y][s.d]+1;
            q.push_back(toCode({s.x, s.y, (s.d+7)&7}));
        }
        if(barrier[s.x+dx[s.d]][s.y+dy[s.d]]==0)
            if(dp[s.x+dx[s.d]][s.y+dy[s.d]][s.d]>dp[s.x][s.y][s.d])
            {
                dp[s.x+dx[s.d]][s.y+dy[s.d]][s.d]=dp[s.x][s.y][s.d];
                q.push_front(toCode({s.x+dx[s.d], s.y+dy[s.d], s.d}));
            }

    }
    out<<-1;
    return 0;
}