Cod sursa(job #2321090)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 17:53:22
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 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;

struct Coada{
    int x,y,dir;
};

queue<Coada> Q,q;

int main()
{
    f>>n>>m;
    f>>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;
    memset(dyn,127,sizeof(dyn));
    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;
    for(i=0;i<8;i++)
    {
        Coada X;
        X.x=in.first;
        X.y=in.second;
        X.dir=i;
        Q.push(X);
        dyn[in.first][in.second][i]=0;
    }
    while(!Q.empty())
    {
        while(!Q.empty())
        {
            Coada tp=Q.front();
            Q.pop();

            Coada nx=tp;
            nx.x+=dirx[nx.dir];
            nx.y+=diry[nx.dir];
            if(!a[nx.x][nx.y])
                if(dyn[nx.x][nx.y][nx.dir]>dyn[tp.x][tp.y][tp.dir])
                {
                    dyn[nx.x][nx.y][nx.dir]=dyn[tp.x][tp.y][tp.dir];
                    q.push(nx);
                }
            nx=tp;
            nx.dir=(nx.dir+1)%8;
            if(dyn[nx.x][nx.y][nx.dir]>dyn[tp.x][tp.y][tp.dir]+1)
            {
                dyn[nx.x][nx.y][nx.dir]=dyn[tp.x][tp.y][tp.dir]+1;
                q.push(nx);
            }
            nx=tp;
            nx.dir=(nx.dir+7)%8;
            if(dyn[nx.x][nx.y][nx.dir]>dyn[tp.x][tp.y][tp.dir]+1)
            {
                dyn[nx.x][nx.y][nx.dir]=dyn[tp.x][tp.y][tp.dir]+1;
                q.push(nx);
            }
        }
        while(!q.empty())
        {
            Q.push(q.front());
            q.pop();
        }
    }
    int ans=1e9;
    for(i=0;i<8;i++)
        ans=min(ans,dyn[out.first][out.second][i]);
    if(ans!=1e9)
        g<<ans;
    else
        g<<-1;
}