Cod sursa(job #3287395)

Utilizator stanciuvalentinStanciu-Tivlea Valentin Gabriel stanciuvalentin Data 17 martie 2025 19:45:50
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("car.in");
ofstream g("car.out");

struct date{
    int i,j,d;
};

bool viz[502][502][9];
int n,m,l1,c1,l2,c2,finish,a[502][502],drum[502][502][9];
const int dx[]={0,-1,-1,0,1,1,1,0,-1}, dy[]={0,0,1,1,1,0,-1,-1,-1};
queue <date> q[1000200];

int dir(int i,int j,int ii,int jj){
    for(int d=1; d<=8; d++)
        if(i+dx[d]==ii and j+dy[d]==jj)
            return d;
}

int cost(int d1,int d2,int i,int j,int ii,int jj){
    if(d1<=d2)
        return min(d2-d1,d1+8-d2);
    return min(d1-d2,d2+8-d1);
}

int dial(int l,int c)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            for(int d=1; d<=8; d++)
                drum[i][j][d]=INT_MAX;
    for(int d=1; d<=8; d++)
    {
        int ii=l+dx[d], jj=c+dy[d];
        if(a[ii][jj]==0)
            q[0].push({l,c,d});
    }
    for(int i=0; i<=n*n*4; i++)
    {
        while(!q[i].empty())
        {
            date x=q[i].front(); q[i].pop();
            if(x.i==l2 and x.j==c2)
                return i;
            if(viz[x.i][x.j][x.d]==0)
            {
                viz[x.i][x.j][x.d]=1;
                for(int d=1; d<=8; d++)
                {
                    int ii=x.i+dx[d], jj=x.j+dy[d];
                    if(a[ii][jj]==0)
                    {
                        int newcost=i+cost(x.d,d,x.i,x.j,ii,jj);
                        if(a[ii][jj]==0 and newcost<drum[ii][jj][d])
                            drum[ii][jj][d]=newcost, q[newcost].push({ii,jj,d});
                    }
                }
            }
        }
    }
    return 0;
}

int32_t main()
{
    f>>n>>m>>l1>>c1>>l2>>c2;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            f>>a[i][j];
    for(int i=0; i<=n+1; i++)
        a[0][i]=a[n+1][i]=1, a[i][0]=a[i][n+1]=1;
    g<<dial(l1,c1);
    return 0;
}