Cod sursa(job #3360670)

Utilizator MirainfoTarta Mira Mirainfo Data 15 iulie 2026 14:04:20
Problema Car Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
/// Car infoarena

#include <fstream>
#include <vector>
#include <deque>
using namespace std;

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

const int N = 500, INF = 1e6+1;;
int n, m, si, sj, fi, fj, dist[N][N][8];
bool city[N][N];

void read()
{
    fin >> n >> m >> si >> sj >> fi >> fj;
    si--; sj--; fi--; fj--;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            fin >> city[i][j];
        }
    }
    fin.close();
}

bool validPosition(int i, int j)
{
    return ((i >= 0) && (i < n) && (j >= 0) && (j < m));
}

void minCost()
{
    /// dist[i][j][direction]
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            for (int d = 0; d < 8; d++)
            {
                dist[i][j][d] = INF;
            }
        }
    }
    int di[] = {-1, -1, -1, 0, 1, 1, 1, 0}, dj[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    deque<tuple<int, int, int>> dq; /// {i, j, direction}
    /**
    directions:
        0 1 2
        7 . 3
        6 5 4
    */
    for (int i = 0; i < 8; i++)
    {
        dq.push_front({si, sj, i});
        dist[si][sj][i] = 0;
    }
    while (!dq.empty())
    {
        auto [i, j, dir] = dq.front();
        dq.pop_front();

        if ((i == fi) && (j == fj)) /// The nodes are processed in increasing distance order, so the first route to (fi, fj) is the minimal one
        {
            fout << dist[i][j][dir];
            fout.close();
            return;
        }

        /// Checking if the car can move in the same direction
        /// 0 degrees, cost 0
        if (validPosition(i+di[dir], j+dj[dir]) && !city[i+di[dir]][j+dj[dir]])
        {
            if (dist[i+di[dir]][j+dj[dir]][dir] > dist[i][j][dir])
            {
                dist[i+di[dir]][j+dj[dir]][dir] = dist[i][j][dir];
                dq.push_front({i+di[dir], j+dj[dir], dir});
            }
        }
        /// For the 45 degrees turns, checking is not required, as the car can make multiple turns before actually moving and these entries only represent turns (maintain position (i, j))
        /// 45 degrees clockwise, cost 1
        if (dist[i][j][(dir+1)%8] > dist[i][j][dir] + 1)
        {
            dist[i][j][(dir+1)%8] = dist[i][j][dir] + 1;
            dq.push_back({i, j, (dir+1)%8});
        }
        /// 45 degrees counterclockwise, cost 1
        if (dist[i][j][(dir+7)%8] > dist[i][j][dir] + 1)
        {
            dist[i][j][(dir+7)%8] = dist[i][j][dir] + 1;
            dq.push_back({i, j, (dir+7) % 8});
        }
    }
    fout << -1;
    fout.close();
}

int main()
{
    read();
    minCost();
    return 0;
}