Cod sursa(job #3282712)

Utilizator InfinitumDanila Laurentiu Infinitum Data 6 martie 2025 15:01:01
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("car.in");
#define cin f
const int NMAX=505, INF=1e9;
bitset<NMAX> a[NMAX];
int n, m,sti, stj, fni, fnj, dir, x,y;

//de la diagonala dreapta sus
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
vector<vector<vector<int>>> d;
deque<tuple<int,int,int>> dq;
void bfs()
{
    int rtdir;
    d.assign(8,vector<vector<int>>(n+1,vector<int>(m+1, INF)));
    for(int i=0; i<8; i++)
    {
        d[i][sti][stj]=0;
        dq.push_back({i, sti, stj});
    }
    while(!dq.empty())
    {
        tie(dir, x, y)=dq.front();
        int px = x+dx[dir];
        int py = y+dy[dir];
        dq.pop_front();
        //la final d[dir][x][y]<d[dir][px][py] este pentru a verifica daca am gasit un
        //drum deja mai scurt decat cel pe care il avem acum
        if(px>=1 && px<=n && py>=1 && py<=m && !a[px][py] && d[dir][x][y]<d[dir][px][py])
        {
            d[dir][px][py]=d[dir][x][y];
            dq.push_front({dir, px, py});
        }
        for(int k=-1; k<=1; k+=2)
        {
            rtdir =(dir+k+8)%8;
            if(d[dir][x][y]+1<d[rtdir][x][y])
            {
                d[rtdir][x][y]=d[dir][x][y]+1;
                dq.push_back({rtdir, x, y});
            }
        }
    }
}
int main()
{

    //in dq avem distanta, coordonate
    cin >> n >> m;

    cin >> sti >> stj >> fni >> fnj;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin >> x;
            a[i][j]=x;
        }
    }
    bfs();
    int t=INF;
    for(int i=0; i<8; i++)
        if(d[i][fni][fnj]<t)
            t=d[i][fni][fnj];
    if(t==INF)
        cout << -1;
    else cout << t;

}