Cod sursa(job #2923622)

Utilizator andreimocianAndrei Mocian andreimocian Data 16 septembrie 2022 20:38:01
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 505;
const int INF = 1e9;
int n, m, a[NMAX][NMAX], si, sj, fi, fj, sol;
int dp[NMAX][NMAX][10];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

struct el
{
    int x, y, dir, cost;
};

queue<el> Q1, Q2;

bool ok(int i, int j)
{
    if (i < 1 || j < 1 || n < i || m < j || a[i][j])
        return false;
    return true;
}

void citire()
{
    el E;
    fin >> n >> m;
    fin >> si >> sj >> fi >> fj;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            fin >> a[i][j];
            for (int k = 0; k < 8; k++)
            {
                dp[i][j][k] = INF;
            }
        }
    }
    for (int k = 0; k < 8; k++)
    {
        E.x = si;
        E.y = sj;
        E.cost = 0;
        E.dir = k;
        Q1.push(E);
    }
}

void Dijkstra()
{
    el E, W;
    while (!Q1.empty())
    {
        while (!Q1.empty())
        {
            E = Q1.front();
            Q1.pop();
            W.cost = E.cost;
            W.dir = E.dir;
            W.x = E.x + dx[E.dir];
            W.y = E.y + dy[E.dir];
            if(ok(W.x, W.y) && dp[W.x][W.y][W.dir] > W.cost)
            {
                dp[W.x][W.y][W.dir] = W.cost;
                Q1.push(W);
            }
            W.cost++;
            W.dir = (E.dir + 1) % 8;
            W.x = E.x;
            W.y = E.y;
            if(ok(W.x, W.y) && dp[W.x][W.y][W.dir] > W.cost)
            {
                dp[W.x][W.y][W.dir] = W.cost;
                Q2.push(W);
            }
            W.dir = E.dir - 1;
            if(W.dir < 0)
                W.dir = 7;
            if(ok(W.x, W.y) && dp[W.x][W.y][W.dir] > W.cost)
            {
                dp[W.x][W.y][W.dir] = W.cost;
                Q2.push(W);
            }
        }
        while (!Q2.empty())
        {
            E = Q2.front();
            Q2.pop();
            Q1.push(E);
        }
    }
}

void solve()
{
    Dijkstra();
    sol = dp[fi][fj][0];
    for(int i = 1; i < 8; i++)
    {
        sol = min(sol, dp[fi][fj][i]);
    }
    if(sol == INF)
        fout << -1;
    else
        fout << sol;
}

int main()
{
    citire();
    solve();
    return 0;
}