Cod sursa(job #3238942)

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

const int nmax = 505, inf = 0x3F3F3F3F;
const int dir = 8;
const int ox[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int oy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n, m, xs, ys, xf, yf;
int dist[nmax][nmax][dir];
bitset<nmax> a[nmax], visited[nmax][dir];
queue<tuple<int, int, int>> q[3];

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

void dial(int xs, int ys) {
    memset(dist, inf, sizeof(dist));

    int current_queue = 0, no_elements = dir;
    for (int i = 0; i < dir; ++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 x, y, direction;
        tie(x, y, direction) = q[current_queue].front();
        q[current_queue].pop();
        --no_elements;

        if (!visited[x][y][direction]) {
            for (int k = -2; k <= 2; ++k) {
                int newdirection = (direction + k + dir) % dir;
                int nx = x + ox[newdirection];
                int ny = y + oy[newdirection];
                if (inside(nx, ny) && !a[nx][ny] && !visited[nx][ny][newdirection] && dist[nx][ny][newdirection] > dist[x][y][direction] + abs(k)) {
                    dist[nx][ny][newdirection] = dist[x][y][direction] + abs(k);
                    q[dist[nx][ny][newdirection] % 3].push({nx, ny, newdirection});
                    ++no_elements;
                }
            }
            visited[x][y][direction] = 1;
        }
    }
}

int main() {
    ifstream cin("car.in");
    ofstream cout("car.out");

    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 < dir; ++i)
        ans = min(ans, dist[xf][yf][i]);

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

    return 0;
}