Cod sursa(job #2321046)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 17:12:31
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>>

using namespace std;

ifstream f("car.in");
ofstream g("car.out");

int n,m,i,j,dirx[10],diry[10],a[510][510],dyn[510][510][10];
pair<int,int> in,out;
queue<pair<pair<int,int>, pair<int,int> > > Q;

int main()
{
    f>>n>>m>>in.first>>in.second>>out.first>>out.second;
    dirx[0]=-1;
    diry[0]= 0;
    dirx[1]=-1;
    diry[1]= 1;
    dirx[2]= 0;
    diry[2]= 1;
    dirx[3]= 1;
    diry[3]= 1;
    dirx[4]= 1;
    diry[4]= 0;
    dirx[5]= 1;
    diry[5]=-1;
    dirx[6]= 0;
    diry[6]=-1;
    dirx[7]=-1;
    diry[7]=-1;
    for(i=1; i<=n; i++)
        for(j=1; j<=m; j++)
            f>>a[i][j];
    for(i=0; i<=n+1; i++)
        a[i][0]=a[i][m+1]=1;
    for(j=0; j<=m+1; j++)
        a[0][j]=a[n+1][j]=1;
    memset(dyn,127,sizeof(dyn));
    for(i=0; i<8; i++)
    {
        Q.push({{0,in.first},{in.second,i}});
        dyn[in.first][in.second][i]=0;
    }
    while(Q.size())
    {
        int cst=-Q.front().first.first;
        pair<int,int> x= {Q.front().first.second,Q.front().second.first};
        int dir=Q.front().second.second;
        Q.pop();
        if(cst>dyn[x.first][x.second][dir])
            continue;
        int val=0;
        for(i=0; i<=4; i++)
        {
            if(!a[x.first+dirx[dir]][x.second+diry[dir]])
                if(dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]>cst+val)
                {
                    dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]=cst+val;
                    Q.push({{-dyn[x.first+dirx[dir]][x.second+diry[dir]][dir],x.first+dirx[dir]},{x.second+diry[dir],dir}});
                }
            dir=(dir+1)%8;
            val++;
        }
        val-=2;
        for(i=0; i<=2; i++)
        {
            if(!a[x.first+dirx[dir]][x.second+diry[dir]])
                if(dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]>cst+val)
                {
                    dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]=cst+val;
                    Q.push({{-dyn[x.first+dirx[dir]][x.second+diry[dir]][dir],x.first+dirx[dir]},{x.second+diry[dir],dir}});
                }
            dir=(dir+1)%8;
            val--;
        }
    }
    int ans=1e9;
    for(i=0; i<=7; i++)
        ans=min(ans,dyn[out.first][out.second][i]);
    if(ans!=1e9)
        g<<ans;
    else
        g<<-1;
    return 0;
}