Cod sursa(job #3346479)

Utilizator CarenaMironov Cezar Luca Carena Data 13 martie 2026 20:13:47
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX=5e2+5, INF=1e9;
int n, m, a[NMAX][NMAX], viz[8][NMAX][NMAX], dist[8][NMAX][NMAX];
struct cell{int d, i, j;}s, f;
deque<cell> dq;
int di[8]={1, 1, 0, -1, -1, -1, 0, 1},
    dj[8]={0, -1, -1, -1, 0, 1, 1, 1};

int mod(int x)
{
    return (x+8)%8;
}

bool valid(cell c)
{
    return ((1<=c.i && c.i<=n) && (1<=c.j && c.j<=m) && !a[c.i][c.j]);
}

void check_cell(cell c, cell nc, bool cst)
{
    dist[nc.d][nc.i][nc.j]=min(dist[nc.d][nc.i][nc.j], dist[c.d][c.i][c.j]+cst);
    if(cst)
        dq.push_back(nc);
    else
        dq.push_front(nc);
}

void BFS01()
{
    for(int d=0;d<8;d++)
    {
        dist[d][s.i][s.j]=0;
        dq.push_front({d, s.i, s.j});
    }
    while(!dq.empty())
    {
        cell c=dq.front(); dq.pop_front();
        if(viz[c.d][c.i][c.j])
            continue;
        viz[c.d][c.i][c.j]=1;
        if(valid({c.d, c.i+di[c.d], c.j+dj[c.d]}))
            check_cell(c, {c.d, c.i+di[c.d], c.j+dj[c.d]}, 0);
        for(int b=-1;b<=1;b+=2)
            check_cell(c, {mod(c.d+b), c.i, c.j}, 1);
    }
}

int main()
{
    in>>n>>m>>s.i>>s.j>>f.i>>f.j;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            in>>a[i][j];
            for(int d=0;d<8;d++)
                dist[d][i][j]=INF;
        }
    BFS01();
    int ans=INF;
    for(int d=0;d<8;d++)
        if(viz[d][f.i][f.j])
            ans=min(ans, dist[d][f.i][f.j]);
    out<<(ans==INF?-1:ans);
    return 0;
}