Cod sursa(job #3313548)

Utilizator prodsevenStefan Albu prodseven Data 5 octombrie 2025 10:35:03
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>

using namespace std;

const int MAX = 505, DIRECTIONS = 8, BUCKET_NR = 3;
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, xs, ys, xf, yf;

bitset<MAX> drum[MAX], viz[8][MAX];
queue<tuple<int, int, int>> q[BUCKET_NR]; // direction, x, y
vector<vector<vector<int>>> dist;

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

inline bool inside(int i, int j) {
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

void dial() {
    int q_number = 0, nr_elements = DIRECTIONS;

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

    while (nr_elements > 0) {
        while (q[q_number].empty()) {
            q_number = (q_number + 1) % BUCKET_NR;
        }

        int direction, x, y;
        tie(direction, x, y) = q[q_number].front();
        q[q_number].pop();
        nr_elements--;

        if (!viz[direction][x][y]) {
            // 90 degrees, 45 degrees left
            for (int k = -2 ; k < 0 ; ++k) {
                int ndirection = (direction + k + 8) % DIRECTIONS;
                int nx = x + dx[ndirection];
                int ny = y + dy[ndirection];

                if (inside(nx, ny) && // inside
                    !drum[nx][ny] && // not obstacle
                    !viz[ndirection][nx][ny] && // not vizited from that direction
                    dist[direction][x][y] - k < dist[ndirection][nx][ny] // distance from before + this cost < previous neighbor distance (this is a better path then)
                ) {
                    // subtract k instead of add because k is negative in the loop, however the operations are still positive cost
                    dist[ndirection][nx][ny] = dist[direction][x][y] - k;
                    nr_elements++;
                    q[(q_number - k) % BUCKET_NR].push({ndirection, nx, ny}); // push in the queue k spots away (cyclically)
                }
            }

            // 0 degrees, 45 degrees, 90 degrees right
            for (int k = 0 ; k < 3 ; ++k) {
                int ndirection = (direction + k) % DIRECTIONS;
                int nx = x + dx[ndirection];
                int ny = y + dy[ndirection];

                // same comments, k is now positive so we add normally
                if (inside(nx, ny) &&
                    !drum[nx][ny] &&
                    !viz[ndirection][nx][ny] &&
                    dist[direction][x][y] + k < dist[ndirection][nx][ny]
                ) {
                    dist[ndirection][nx][ny] = dist[direction][x][y] + k;
                    nr_elements++;
                    q[(q_number + k) % BUCKET_NR].push({ndirection, nx, ny});
                }
            }
            viz[direction][x][y] = 1; // relaxed, we checked all neighbors
        }
    }
}

int main() {
    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;
            drum[i][j] = x;
        }
    }
    dist.resize(DIRECTIONS, vector<vector<int>>(n + 2, vector<int>(m + 1, INT_MAX)));
    dial();
    int ans = INT_MAX;
    // check from which direction the distance is smallest
    for (int i = 0 ; i < DIRECTIONS ; ++i) {
        if (dist[i][xf][yf] < ans) ans = dist[i][xf][yf];
    }
    cout << (ans == INT_MAX ? -1 : ans);
    return 0;
}