Cod sursa(job #2979283)

Utilizator Horia_haivasHaivas Horia Horia_haivas Data 14 februarie 2023 21:30:45
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.16 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
{
    int lin;
    int col;
    int direction;
    int cost;
};

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

int main()
{
    ifstream fin("car.in");
    ofstream fout("car.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,si,sj,fi,fj,i,j,l,c;
    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])
            {
                distans[frontnode.lin][frontnode.col]=frontnode.cost;
                visited[frontnode.lin][frontnode.col]=1;
                for (i=0; i<8; i++)
                {
                    l=frontnode.lin;
                    c=frontnode.col;
                    l+=dlin[i];
                    c+=dcol[i];
                    if (!visited[l][c] && !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();
    }
    if (visited[fi][fj])
    fout << distans[fi][fj];
    else
    fout << -1;
}