Cod sursa(job #2321052)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 17:14:40
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 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,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.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--;
            }
        }
        while(q.size())
        {
            Q.push(q.front());
            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;
}