Cod sursa(job #2670693)

Utilizator stefantagaTaga Stefan stefantaga Data 10 noiembrie 2020 15:35:17
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>
#define INF 1000000005
using namespace std;
ifstream f("car.in");
ofstream g("car.out");
int din[501][501][8];
int dl[]={-1,-1,0,1,1,1,0,-1};
int dc[]={0,1,1,1,0,-1,-1,-1};
int cost[8][8],x2,y2,i,j,n,m,k,xcur,ycur;
int ok[501][501];
struct wow
{
    int x,y,dir;
};
bool interior (int x,int y)
{
    if (1<=x&&x<=n&&1<=y&&y<=m)
    {
        if (ok[x][y]==0)
        {
            return 1;
        }
    }
    return 0;
}
bool verif ()
{
    int i;
    for (i=0;i<=7;i++)
    {
        if (din[x2][y2][i]!=INF)
        {
            return 1;
        }
    }
    return 0;
}
int x,y;
priority_queue < pair < pair <int,int> , pair <int,int> > , vector <pair < pair <int,int> , pair <int,int> >> , greater < pair < pair <int,int> , pair <int,int> > > > h;
int main()
{
    f>>n>>m;
    f>>x>>y>>x2>>y2;
    for (int i=0;i<8;i++){
        for (int j=0;j<8;j++){
            cost[i][j] = min(abs(j-i), 8 - max(i,j) + min(i,j));
        }
    }

    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            f>>ok[i][j];
        }
    }
    if (ok[x][y]==1||ok[x2][y2]==1)
    {
        g<<"-1";
        return 0;
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            for (k=0;k<=7;k++)
            {
                din[i][j][k]=INF;
            }
        }
    }
    for (i=0;i<=7;i++)
    {
        din[x][y][i]=0;
        xcur=x+dl[i];
        ycur=y+dc[i];
        if (interior(xcur,ycur)==1)
        {
            din[xcur][ycur][i]=0;
            h.push({{0,i},{xcur,ycur}});
        }
    }
    while (!h.empty())
    {
        pair <pair <int,int> , pair <int,int>  >  acum=h.top();
        h.pop();
        if (acum.second.first==x2&&acum.second.second==y2)
        {
            g<<acum.first.first;
            return 0;
        }
             for (i=0;i<=7;i++)
        {
             xcur=acum.second.first+dl[i];
             ycur=acum.second.second+dc[i];
             if (interior(xcur,ycur)==1&&din[xcur][ycur][i]>acum.first.first+cost[acum.first.second][i]&&cost[acum.first.second][i]!=4)
             {
                 din[xcur][ycur][i]=acum.first.first+cost[acum.first.second][i];
                 h.push({{din[xcur][ycur][i],i},{xcur,ycur}});
             }
        }

    }
    g<<"-1";
    return 0;
}