Cod sursa(job #2854359)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 21 februarie 2022 11:51:14
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define ll long long
#define ull unsigned long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define EPSILON 0.000001

using namespace std;

const ll NMAX = 1e5+5, INF = 1e18, MOD = 1e9 + 7, MMAX = 1e2 + 5, inf = INT_MAX;

ifstream fin("car.in");
ofstream fout("car.out");

int N,M,xs,ys,xf,yf;
int dp[505][505][8],dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
bool v[505][505],vis[505][505][8];

struct str
{
    int cost,x,y,dir;
};

deque<str> dq;

bool ok(int x,int y)
{
    if(x==0||x==N+1||y==0||y==M+1||v[x][y])return 0;
    return 1;
}

void bfs()
{
    for(int p=0;p<8;p++)
    {
        dq.push_front({0,xs,ys,p});
        dp[xs][ys][p]=0;
    }
    while(!dq.empty())
    {
        int cost=dq.front().cost;
        int x=dq.front().x;
        int y=dq.front().y;
        int dir=dq.front().dir;
        dq.pop_front();

        if(vis[x][y][dir])
            continue;

        vis[x][y][dir]=1;

        int new_dir=dir;
        int x1=x+dx[new_dir];
        int y1=y+dy[new_dir];
        if(ok(x1,y1))
        {
            if(cost<dp[x1][y1][dir])
            {
                dp[x1][y1][dir]=cost;
                dq.push_front({cost,x1,y1,dir});
            }
        }
        new_dir=(dir+1)%8;
        if(cost+1<dp[x][y][new_dir])
        {
            dp[x][y][new_dir]=cost+1;
            dq.push_back({cost+1,x,y,new_dir});
        }
        new_dir=(dir-1+8)%8;
        if(cost+1<dp[x][y][new_dir])
        {
            dp[x][y][new_dir]=cost+1;
            dq.push_back({cost+1,x,y,new_dir});
        }
    }
    int ans=1e9;
    for(int p=0;p<8;p++)
    {
        ans=min(ans,dp[xf][yf][p]);
    }
    if(ans==1e9)fout<<-1;
    else fout<<ans;
}

int main()
{
    cin.tie ( 0 )->sync_with_stdio ( 0 );
    cin.tie ( NULL );
    cout.tie ( NULL );

    fin>>N>>M>>xs>>ys>>xf>>yf;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            fin>>v[i][j];
            for(int p=0;p<8;p++)
            {
                dp[i][j][p]=1e9;
            }
        }
    }
    bfs();

    return 0;
}