Cod sursa(job #2327503)

Utilizator MAXIMILLIANMUSOHYEAHYEAH MAXIMILLIANMUS Data 24 ianuarie 2019 19:15:47
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 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;
}