Submission #1342729

#TimeUsernameProblemLanguageResultExecution timeMemory
1342729valerianText editor (CEOI24_editor)C++20
0 / 100
4103 ms267648 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define Valerian void
#define Valerian_or_Habil ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

Valerian solve() {
    int n;
    cin >> n;
    int sl, sc, el, ec;
    cin >> sl >> sc >> el >> ec;
    
    vector<int> l(n + 1);
    for (int i = 1; i <= n; i++) cin >> l[i];

    queue<pair<int, int>> q;
    q.push({sl, sc});

    map<pair<int, int>, int> dist;
    dist[{sl, sc}] = 0;

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        int r = curr.first;
        int c = curr.second;
        int d = dist[curr];
        q.pop();

        if (r == el && c == ec) {
            cout << d << endl;
            return;
        }

        vector<pair<int, int>> moves;

        if (c > 1) moves.pb({r, c - 1});
        else if (r > 1) moves.pb({r - 1, l[r - 1] + 1});

        if (c < l[r] + 1) moves.pb({r, c + 1});
        else if (r < n) moves.pb({r + 1, 1});

        if (r > 1) moves.pb({r - 1, min(c, l[r - 1] + 1)});
        if (r < n) moves.pb({r + 1, min(c, l[r + 1] + 1)});

        for (auto &m : moves) {
            if (dist.find(m) == dist.end()) {
                dist[m] = d + 1;
                q.push(m);
            }
        }
    }
}

int main() {
    Valerian_or_Habil;
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...