Cod sursa(job #2321076)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 17:33:46
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.46 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;
priority_queue<pair<pair<int,int>, pair<int,int> > > Q,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())
    {
        while(Q.size())
        {
            int cst=-Q.top().first.first;
            pair<int,int> x= {Q.top().first.second,Q.top().second.first};
            int dir=Q.top().second.second;
            Q.pop();
            //cout<<x.first<<' '<<x.second<<' '<<dir<<' '<<cst<<'\n';
            if(cst>dyn[x.first][x.second][dir])
                continue;
            if(!a[x.first+dirx[dir]][x.second+diry[dir]])
                if(dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]>
                        dyn[x.first][x.second][dir])
                {
                    dyn[x.first+dirx[dir]][x.second+diry[dir]][dir]=dyn[x.first][x.second][dir];
                    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;
            if(dyn[x.first][x.second][dir]>cst+1)
            {
                dyn[x.first][x.second][dir]=cst+1;
                q.push({{-cst-1,x.first},{x.second,dir}});
            }
            dir=(dir-2+8)%8;
            if(dyn[x.first][x.second][dir]>cst+1)
            {
                dyn[x.first][x.second][dir]=cst+1;
                q.push({{-cst-1,x.first},{x.second,dir}});
            }
        }
        while(q.size())
        {
            Q.push(q.top());
            q.pop();
        }
    }
    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;
}