Cod sursa(job #2820573)

Utilizator puica2018Puica Andrei puica2018 Data 20 decembrie 2021 20:06:07
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m,si,sj,fi,fj;
int a[505][505],cost[8][8],dp[8][505][505];
int dx[8]={-1,0,1,1,1,0,-1,-1};
int dy[8]={1,1,1,0,-1,-1,-1,0};

/// 670
/// 5 1
/// 432

struct atom
{
    int d,x,y,c;
    bool operator < (const atom b) const
    {
        return c>b.c;
    }
};

priority_queue <atom> pq;

void update(atom x)
{
    if(dp[x.d][x.x][x.y]>x.c)
    {
        dp[x.d][x.x][x.y]=x.c;
        pq.push(x);
    }
}

int main()
{
    fin>>n>>m>>si>>sj>>fi>>fj;
    int i,j;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            fin>>a[i][j];
    for(i=0; i<8; i++)
    {
        for(j=0; j<8; j++)
        {
            int t=(j-i+8)%8;
            cost[i][j]=t%5;
        }
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            for(int d=0; d<8; d++)
                dp[d][i][j]=1e9;
    dp[7][si][sj]=0;
    pq.push({7,si,sj,0});
    while(!pq.empty())
    {
        atom x=pq.top(); pq.pop();
        if(dp[x.d][x.x][x.y]<x.c)
            continue;
        if(x.x==fi && x.y==fj)
        {
            fout<<x.c<<"\n";
            return 0;
        }
        for(int dir=0; dir<8; dir++)
        {
            int iv=x.x+dx[dir],jv=x.y+dy[dir];
            if(iv<1 || iv>n || jv<1 || jv>m)
                continue;
            if(a[iv][jv]==1)
                continue;
            atom y;
            y.d=dir; y.x=iv; y.y=jv; y.c=x.c+cost[x.d][dir];
            update(y);
        }
    }
    fout<<"-1\n";
    return 0;
}