Cod sursa(job #2978579)

Utilizator Horia_haivasHaivas Horia Horia_haivas Data 13 februarie 2023 21:57:26
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.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
{
    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[501][501];
int distans[501][501];
bool visited[501][501];

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<4 && frontnode.direction<4 || i>=4 && frontnode.direction>=4)
                        q2.push({l,c,i,frontnode.cost+2});
                        else
                        q1.push({l,c,i,frontnode.cost+1});
                    }
                }
            }
            q0.pop();
        }
        qaux=q2;
        q0=q1;
        q1=qaux;
        while (!q2.empty())
            q2.pop();
    }
    fout << distans[fi][fj];
}