Cod sursa(job #3255301)

Utilizator AndreiNicolaescuEric Paturan AndreiNicolaescu Data 10 noiembrie 2024 09:19:04
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>
using namespace std;

const int DIRECTIONS = 8;
const int INF = 0x3F3F3F3F;
const int Nmax = 503;
const int di[]= {-1,-1,-1,0,1,1,1,0};
const int dj[]= {-1,0,1,1,1,0,-1,-1};
int n, m, x, a[Nmax][Nmax], xs, ys, xf, yf;
vector<vector<vector<int>>> d;
bool viz[Nmax][Nmax][DIRECTIONS];
bool inmat(int i , int j)
{
    return i>=1 && j>=1 && i<=n && j<=m;
}
void bfs(int xs, int ys)
{
    deque<tuple<int, int, int>> dq;
    for(int i=0; i<DIRECTIONS; i++)
    {
        d[xs][ys][i] = 0;
        dq.push_front({xs, ys, i});
    }
    int i, j, dir;
    while(!dq.empty())
    {
        tie(i, j, dir) = dq.front();
        dq.pop_front();
        if(!viz[i][j][dir])
        {
            int inou = i + di[dir];
            int jnou = j + dj[dir];
            if(inmat(inou, jnou) && !a[inou][jnou] && !viz[inou][jnou][dir] && d[inou][jnou][dir] > d[i][j][dir])
            {
                d[inou][jnou][dir] = d[i][j][dir];
                dq.push_front({inou, jnou, dir});
            }
            else
            {
                int inou = i;
                int jnou = j;
                int dirnou = ((dir - 1) + 8) % DIRECTIONS;
                if(inmat(inou, jnou) && !a[inou][jnou] && !viz[inou][jnou][dirnou] && d[inou][jnou][dirnou] > d[i][j][dir] + 1)
                {
                    d[inou][jnou][dirnou] = d[i][j][dir] + 1;
                    dq.push_back({inou, jnou, dirnou});
                }

                inou = i;
                jnou = j;
                dirnou = (dir + 1)  % DIRECTIONS;
                if(inmat(inou, jnou) && !a[inou][jnou] && !viz[inou][jnou][dirnou] && d[inou][jnou][dirnou] > d[i][j][dir] + 1)
                {
                    d[inou][jnou][dirnou] = d[i][j][dir] + 1;
                    dq.push_back({inou, jnou, dirnou});
                }
            }
            viz[i][j][dir] = 1;
        }
    }
}
int main()
{
    ifstream cin("car.in");
    ofstream cout("car.out");
    cin >> n >> m;
    d.assign(n+1,vector<vector<int>>(m+1,vector<int>(DIRECTIONS,INF)));
    cin >> xs >> ys >> xf >> yf;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> a[i][j];
    bfs(xs, ys);
    long long ans = 0x3F3F3F3F;
    for(int i=0; i<DIRECTIONS; i++)
        ans = min(ans, 1LL * d[xf][yf][i]);
    if(ans == INF)
        cout << "-1";
    else
        cout << ans;
    return 0;
}