Cod sursa(job #3238939)

Utilizator GabrielPopescu21Silitra Gabriel - Ilie GabrielPopescu21 Data 31 iulie 2024 16:40:08
Problema Car Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>
using namespace std;

int dist[505][505][8], n, m;
queue<tuple<int,int,int>> q[3];
bitset<505> a[505], visited[505][8];
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int INF = 0x3F3F3F3F;

bool inside(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

void dial(int xs, int ys)
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 0; k < 8; ++k)
                dist[i][j][k] = INF;

    memset(visited, 0, sizeof(visited));

    int current_queue = 0, no_elements = 8;
    for (int i = 0; i < 8; ++i)
    {
        q[current_queue].push({xs, ys, i});
        dist[xs][ys][i] = 0;
    }

    while (no_elements > 0)
    {
        while (q[current_queue].empty())
            current_queue = (current_queue + 1) % 3;

        int i, j, dir;
        tie(i, j, dir) = q[current_queue].front();
        q[current_queue].pop();
        --no_elements;

        if (!visited[i][j][dir])
        {
            for (int k = -2; k <= -1; ++k) // left [-2, -1]
            {
                int new_dir = (dir + k + 8) % 8;
                int x = i + dx[new_dir];
                int y = j + dy[new_dir];
                if (inside(x, y) && !a[x][y] && !visited[x][y][new_dir] && dist[x][y][new_dir] > dist[i][j][dir]-k)
                {
                    dist[x][y][new_dir] = dist[i][j][dir]-k;
                    q[dist[x][y][new_dir] % 3].push({x, y, new_dir});
                    ++no_elements;
                }
            }

            for (int k = 0; k <= 2; ++k) // right [0, 2]
            {
                int new_dir = (dir + k) % 8;
                int x = i + dx[new_dir];
                int y = j + dy[new_dir];
                if (inside(x, y) && !a[x][y] && !visited[x][y][new_dir] && dist[x][y][new_dir] > dist[i][j][dir]+k)
                {
                    dist[x][y][new_dir] = dist[i][j][dir]+k;
                    q[dist[x][y][new_dir] % 3].push({x, y, new_dir});
                    ++no_elements;
                }
            }

            visited[i][j][dir] = 1;
        }
    }
}

int main()
{
    ifstream cin("car.in");
    ofstream cout("car.out");
    int xs, ys, xf, yf;

    cin >> n >> m >> xs >> ys >> xf >> yf;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            int x;
            cin >> x;
            a[i][j] = x;
        }

    dial(xs, ys);

    int ans = INF;
    for (int i = 0; i < 8; ++i)
        ans = min(ans, dist[xf][yf][i]);

    if (ans == INF)
        cout << -1;
    else
        cout << ans;

    return 0;
}