제출 #1342732

#제출 시각아이디문제언어결과실행 시간메모리
1342732valerianText editor (CEOI24_editor)C++20
14 / 100
585 ms1114112 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);
    int max_c = 0;
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
        max_c = max(max_c, l[i] + 1);
    }

    if (sl == el && sc == ec) {
        cout << 0 << endl;
        return;
    }

    vector<vector<int>> dist(n + 1, vector<int>(max_c + 1, -1));
    queue<pair<int, int>> q;

    q.push({sl, sc});
    dist[sl][sc] = 0;

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        int r = curr.first;
        int c = curr.second;
        int d = dist[r][c];
        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) {
            int nr = m.first;
            int nc = m.second;
            if (dist[nr][nc] == -1) {
                dist[nr][nc] = d + 1;
                q.push({nr, nc});
            }
        }
    }
}

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...