Cod sursa(job #2925930)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 16 octombrie 2022 13:45:03
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

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

typedef pair <pair <int, int>, int> PIII;
constexpr int NMAX = 502;

int N, M;
int Start_i, Start_j, End_i, End_j;
int A[NMAX][NMAX];

void Read () {
    f >> N >> M;

    f >> Start_i >> Start_j;
    f >> End_i >> End_j;

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j )
            f >> A[i][j];
}

int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

bool Good (int x, int y) {
    return (0 < x && x <= N && 0 < y && y <= M && A[x][y] == 0);
}

int Best[NMAX][NMAX][8];

void Solve () {
    if (A[Start_i][Start_j] == -1 || A[End_i][End_j] == -1) {
        g << -1 << '\n';
        return;
    }

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j )
            for (int k = 0; k < 8; ++ k )
                Best[i][j][k] = -1;

    queue < PIII > Q;

    for (int k = 0; k < 8; ++ k ) {
        Best[Start_i][Start_j][k] = 0;
        Q.push({{Start_i, Start_j}, k});
    }

    while (!Q.empty()) {
        PIII nod = Q.front();
        Q.pop();

        int x = nod.first.first;
        int y = nod.first.second;
        int k = nod.second;

        int new_x = x + dx[k];
        int new_y = y + dy[k];

        if (Good(new_x, new_y) && (Best[new_x][new_y][k] == -1 || Best[new_x][new_y][k] > Best[x][y][k])) {
            Best[new_x][new_y][k] = Best[x][y][k];
            Q.push({{new_x, new_y}, k});
        }

        for (int o = -1; o <= 1; o += 2) {
            int new_k = k + o;

            if (new_k < 0) new_k = 7;
            if (new_k > 7) new_k = 0;

            if (Best[x][y][new_k] == -1 || Best[x][y][new_k] > Best[x][y][k] + 1) {
                Best[x][y][new_k] = Best[x][y][k] + 1;
                Q.push({{x, y}, new_k});
            }
        }
    }

    int ans = -1;

    for (int i = 0; i < 8; ++ i ) {
        if (Best[End_i][End_j][i] == -1) continue;

        if (ans == -1 || ans > Best[End_i][End_j][i])
            ans = Best[End_i][End_j][i];
    }

    g << ans << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}