Cod sursa(job #2449895)

Utilizator armigheGheorghe Liviu Armand armighe Data 21 august 2019 01:05:29
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include<cstdio>
#include<fstream>
#include<queue>
using namespace std;
FILE *f=fopen("car.in","r");
ofstream g("car.out");
int a[502][502],d[502][502][10];
int dx[]={0,0,1,1,1,0,-1,-1,-1,0};
int dy[]={0,1,1,0,-1,-1,-1,0,1,0};
struct elem
{
    int x,y,dir;
};
queue<elem>q0,q1;
elem p;
int main()
{
    int n,m,i,j,x1,x2,y1,y2,k,q,sol=2000000000;
    fscanf(f,"%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
        fscanf(f,"%d",&a[i][j]);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    for(k=1;k<=8;k++)
        d[i][j][k]=2000000000;
    for(k=1;k<=8;k++)
    {
        for(i=0;i<=n+1;i++)
            d[i][0][k]=d[i][m+1][k]=-1;
        for(i=0;i<=m+1;i++)
            d[0][i][k]=d[n+1][i][k]=-1;
        d[x1][y1][k]=0;
    }
    for(i=1;i<=8;i++)
    if(a[x1][y1]==0)
        q0.push(elem{x1,y1,i});
    while(!q0.empty())
    {
        while(!q0.empty())
        {
            p=q0.front();
            q0.pop();
            if(a[p.x+dx[p.dir]][p.y+dy[p.dir]]==0&&d[p.x+dx[p.dir]][p.y+dy[p.dir]][p.dir]>d[p.x][p.y][p.dir])
            {
                d[p.x+dx[p.dir]][p.y+dy[p.dir]][p.dir]=d[p.x][p.y][p.dir];
                q0.push(elem{p.x+dx[p.dir],p.y+dy[p.dir],p.dir});
            }
            q=(p.dir+1)%8;
            if(a[p.x][p.y]==0&&d[p.x][p.y][q]>d[p.x][p.y][p.dir]+1)
            {
                d[p.x][p.y][q]=d[p.x][p.y][p.dir]+1;
                q1.push(elem{p.x,p.y,q});
            }
            q=p.dir-1;
            if(q==0)
                q=8;
            if(a[p.x][p.y]==0&&d[p.x][p.y][q]>d[p.x][p.y][p.dir]+1)
            {
                d[p.x][p.y][q]=d[p.x][p.y][p.dir]+1;
                q1.push(elem{p.x,p.y,q});
            }
        }
        while(!q1.empty())
        {
            q0.push(q1.front());
            q1.pop();
        }
    }
    for(i=1;i<=8;i++)
    if(d[x2][y2][i]<sol)
        sol=d[x2][y2][i];
    if(sol==2000000000)
        g<<-1;
    else
        g<<sol;
    return 0;
}