Cod sursa(job #3340384)

Utilizator postolacheepostolache postolachee Data 13 februarie 2026 23:28:52
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define pb push_back
using namespace std;
//#define MOD 1999999973

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

bool inmat(int x, int y) {
    if (1 <= x && x <= n && 1 <= y && y <= m) return true;
    return false;
}

struct state {
    int x, y;
    int dir;
    state (){
        dir = -1;
    }
};

int find_diff(int a, int b) {
    int x = min (abs(a - b), abs(8 - abs(a - b)));
    return x;
}

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

    cin >> n >> m;
    int s1, s2, e1 ,e2;
    cin >> s1 >> s2 >> e1 >> e2;

    vector < vector <int>> a(n + 2, vector <int>(m + 2, 0));
    vector <vector <vector <int>>> dist(n + 2, vector <vector <int>>(m + 2, vector <int>(8, 1e9)));

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

    deque<state> dq;

    state aux;
    aux.x = s1;
    aux.y = s2;

    for (int d = 0; d < 8; d++) {
        dist[s1][s2][d] = 0;
        aux.dir = d;
        dq.push_back(aux);
    }

    while (!dq.empty()) {
        aux = dq.front();
        dq.pop_front();

        int x = aux.x;
        int y = aux.y;
        int dir = aux.dir;
        int costi = dist[x][y][dir];

        int nx = x + dx[dir];
        int ny = y + dy[dir];

        if (inmat(nx, ny) && a[nx][ny] == 0) {
            if (dist[nx][ny][dir] > costi) {
                dist[nx][ny][dir] = costi;

                aux.x = nx;
                aux.y = ny;

                dq.push_front(aux);
            }
        }

        int opt1 = (dir + 1) % 8;// 1 cost | ^ 0 cost
        int opt2 = (dir + 7) % 8;

        if (dist[x][y][opt1] > costi + 1) {
            dist[x][y][opt1] = costi + 1;

            aux.x = x; aux.y = y;
            aux.dir = opt1;

            dq.push_back(aux);
        }

        if (dist[x][y][opt2] > costi + 1) {
            dist[x][y][opt2] = costi + 1;

            aux.x = x; aux.y = y;
            aux.dir = opt2;

            dq.push_back(aux);
        }
    }
    int minn = 1e9;
    for (int d=0;d < 8;d++) minn = min (minn , dist[e1][e2][d]);

    if (minn == 1e9) cout << -1 << "\n";
     else cout << minn << "\n";

    return 0;
}