Cod sursa(job #2979314)

Utilizator Horia_haivasHaivas Horia Horia_haivas Data 14 februarie 2023 21:52:53
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.38 kb
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;

struct coord
{
    short int lin;
    short int col;
    short int direction;
    int cost;
};

queue <coord> q0,q1,q2,qaux;
short int dlin[9] = {1, 1, -1, -1, 1, -1, 0, 0};
short int dcol[9] = {1, -1, 1, -1, 0, 0, 1, -1};
bool a[503][503];
int distans[503][503][9];
bool visited[503][503][9];

int main()
{
    ifstream fin("car.in");
    ofstream fout("car.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    short int n,m,si,sj,fi,fj,i,j,l,c,mi;
    coord frontnode;
    fin >> n >> m;
    fin >> si >> sj >> fi >> fj;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            fin >> a[i][j];
        }
    }
    for (i=0; i<=n+1; i++)
    {
        a[i][0]=1;
        a[i][m+1]=1;
    }
    for (i=0; i<=m+1; i++)
    {
        a[0][i]=1;
        a[n+1][i]=1;
    }
    for (i=0; i<8; i++)
    {
        l=si;
        c=sj;
        l+=dlin[i];
        c+=dcol[i];
        if (!a[l][c])
            q0.push({l,c,i,0});
    }
    while (!q0.empty() || !q1.empty() || !q2.empty())
    {
        while (!q0.empty())
        {
            frontnode=q0.front();
            if (!visited[frontnode.lin][frontnode.col][frontnode.direction])
            {
                distans[frontnode.lin][frontnode.col][frontnode.direction]=frontnode.cost;
                visited[frontnode.lin][frontnode.col][frontnode.direction]=1;
                for (i=0; i<8; i++)
                {
                    l=frontnode.lin;
                    c=frontnode.col;
                    l+=dlin[i];
                    c+=dcol[i];
                    if (!visited[l][c][i] && !a[l][c])
                    {
                        if (i==frontnode.direction)
                            q0.push({l,c,i,frontnode.cost});
                        else if ((i==0 && (frontnode.direction==4 || frontnode.direction==6)) || (i==1 && (frontnode.direction==7 || frontnode.direction==4)) || (i==2 && (frontnode.direction==6 || frontnode.direction==5)) || (i==3 && (frontnode.direction==5 || frontnode.direction==7)) || (i==4 && (frontnode.direction==0 || frontnode.direction==1)) || (i==5 && (frontnode.direction==2 || frontnode.direction==3)) || (i==6 && (frontnode.direction==0 || frontnode.direction==2)) || (i==7 && (frontnode.direction==1 || frontnode.direction==3)))
                            q1.push({l,c,i,frontnode.cost+1});
                        else if (((i==0 || i==3) && (frontnode.direction==1 || frontnode.direction==2)) || ((i==1 || i==2) && (frontnode.direction==0 || frontnode.direction==3)) || ((i==4 || i==5) && (frontnode.direction==6 || frontnode.direction==7)) || ((i==6 || i==7) && (frontnode.direction==4 || frontnode.direction==5)))
                            q2.push({l,c,i,frontnode.cost+2});
                    }
                }
            }
            q0.pop();
        }
        qaux=q2;
        q0=q1;
        q1=qaux;
        while (!q2.empty())
            q2.pop();
    }
    mi=n*m*n;
    for (i=0; i<8; i++)
    {
        if (visited[fi][fj][i])
            mi=min(mi,distans[fi][fj][i]);
    }
    if (mi==(n*m*n))
        fout << -1;
    else
        fout << mi;
}