Cod sursa(job #2670684)

Utilizator stefantagaTaga Stefan stefantaga Data 10 noiembrie 2020 15:11:06
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 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;
queue <wow> q;
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++)
    {
        xcur=x+dl[i];
        ycur=y+dc[i];
        if (interior(xcur,ycur)==1)
        {
            din[xcur][ycur][i]=0;
            q.push(wow{xcur,ycur,i});
        }
    }
    while (!q.empty())
    {
        wow acum=q.front();
        q.pop();
        for (i=0;i<=7;i++)
        {
             xcur=acum.x+dl[i];
             ycur=acum.y+dc[i];
             if (interior(xcur,ycur)==1&&din[xcur][ycur][i]>din[acum.x][acum.y][acum.dir]+cost[acum.dir][i])
             {
                 din[xcur][ycur][i]=din[acum.x][acum.y][acum.dir]+cost[acum.dir][i];
                 q.push(wow{xcur,ycur,i});
             }
        }
    }
    if (verif()==0)
    {
        g<<"-1"<<'\n';
        return 0;
    }
    int minim=INF;
    for (j=0;j<=7;j++)
    {
        if (din[x2][y2][j]<minim)
        {
            minim=din[x2][y2][j];
        }
    }
    g<<minim;
    return 0;
}