Cod sursa(job #3321071)

Utilizator MihneaStoicaMihnea Teodor Stoica MihneaStoica Data 8 noiembrie 2025 10:13:33
Problema Car Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;

#if 0
#define int ll
#define uint ull
#endif

int dirl[8] = {-1, -1, 0, 1, 1, 1, 0, -1},
    dirc[8] = {0, 1, 1, 1, 0, -1, -1, -1};

void tc() {
    int n, m; cin >> n >> m;
    int si, sj, fi, fj; cin >> si >> sj >> fi >> fj;
    vector<vector<int>> mat(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> mat[i][j];
        }
    }
    vector<vector<vector<int>>> minn(n + 1, vector<vector<int>>(m + 1, vector<int>(8, INT32_MAX)));

    queue<tuple<int, int, int>> q;
    for (int dir = 0; dir < 8; dir ++) {
        minn[si][sj][dir] = 0;
        q.push({si, sj, dir});
    }

    while (!q.empty()) {
        auto [x, y, dir] = q.front(); q.pop();

        for (int dir2 = 0; dir2 < 8; dir2 ++) {
            int xx = x + dirl[dir2], yy = y + dirc[dir2];
            // cout << min((dir - dir2 + 8) % 8, (dir2 - dir + 8) % 8) << " for " << dir << " -> " << dir2 << '\n';
            if (1 <= xx && xx <= n && 1 <= yy && yy <= m && !mat[xx][yy] &&
                minn[x][y][dir] + min((dir - dir2 + 8) % 8, (dir2 - dir + 8) % 8) < minn[xx][yy][dir2]    
            ) {
                minn[xx][yy][dir2] = minn[x][y][dir] + min((dir - dir2 + 8) % 8, (dir2 - dir + 8) % 8);
                q.push({xx, yy, dir2});
            }
        }
    }

    cout << *min_element(minn[fi][fj].begin(), minn[fi][fj].end()) << '\n';
}

#define MTC 0
#define FIO 1
#define FN "car"

signed main() {
#if FIO == 1 && !defined(LOCAL)
    (void)freopen(FN ".in", "r", stdin);
    (void)freopen(FN ".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#if MTC == 1
    signed tt; cin >> tt;
    while (tt --) tc();
#else
    tc();
#endif
    return 0;
}