Cod sursa(job #3130841)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 18 mai 2023 18:17:32
Problema Car Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int max_size = 5e2 + 1, INF = 2e9 + 1;

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

int dp[12][max_size][max_size], a[max_size][max_size], n, m, /// intervalu de directii reale e [2, 9]
dx[] = {0, -1, -1, -1, 0, 1, 1, 1, 0, -1, -1, -1},
dy[] = {-1, -1, 0, 1, 1, 1, 0, -1, -1, -1, 0, 1};
queue <str> q[3];

void bfs (int xs, int ys)
{
    for (int k = 0; k <= 11; k++)
    {
        dp[k][xs][ys] = 0;
    }
    for (int k = 2; k <= 9; k++)
    {
        q[0].push({k, xs, ys, 0});
    }
    while (!q[1].empty() || !q[2].empty() || !q[0].empty())
    {
        int ind = 0, mn = INF;
        for (int i = 0; i <= 2; i++)
        {
            if (q[i].empty())
            {
                continue;
            }
            if (q[i].front().cost < mn)
            {
                mn = q[i].front().cost;
                ind = i;
            }
        }
        int dir = q[ind].front().dir, i = q[ind].front().x, j = q[ind].front().y;
        q[ind].pop();
        for (int k = dir - 2; k <= dir + 2; k++)
        {
            int iv = i + dx[k], jv = j + dy[k], nd = k;
            if (nd == 0)
            {
                nd = 8;
            }
            if (nd == 1)
            {
                nd = 9;
            }
            if (nd == 10)
            {
                nd = 2;
            }
            if (nd == 11)
            {
                nd = 3;
            }
            if (a[iv][jv] == 0 && dp[dir][i][j] + abs(dir - k) < dp[nd][iv][jv])
            {
                dp[nd][iv][jv] = dp[dir][i][j] + abs(dir - k);
                int cost = abs(dir - k);
                if (cost == 0)
                {
                    q[0].push({nd, iv, jv, dp[nd][iv][jv]});
                }
                if (cost == 1)
                {
                    q[1].push({nd, iv, jv, dp[nd][iv][jv]});
                }
                if (cost == 2)
                {
                    q[2].push({nd, iv, jv, dp[nd][iv][jv]});
                }
            }
        }
    }
}

int main ()
{
    int xs, ys, xf, yf;
    in >> n >> m >> xs >> ys >> xf >> yf;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int k = 0; k <= 11; k++)
            {
                dp[k][i][j] = INF;
            }
            in >> a[i][j];
        }
    }
    bfs(xs, ys);
    int ans = INF;
    for (int k = 0; k <= 11; k++)
    {
        ans = min(ans, dp[k][xf][yf]);
    }
    out << ans;
    in.close();
    out.close();
    return 0;
}