제출 #1084627

#제출 시각아이디문제언어결과실행 시간메모리
1084627SulAText editor (CEOI24_editor)C++17
14 / 100
83 ms24972 KiB
#include <bits/stdc++.h>
using namespace std;

void subtask_1_2(int n) {
    pair<int,int> start, end;
    cin >> start.first >> start.second >> end.first >> end.second;

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

    int dist[n+1][5002];
    bool vis[n+1][5002] = {};
    queue<pair<int,int>> q;
    q.push(start);
    vis[start.first][start.second] = true;
    dist[start.first][start.second] = 0;

    auto visit = [&](int to_x, int to_y, int from_x, int from_y) {
        if (!vis[to_x][to_y]) {
            dist[to_x][to_y] = dist[from_x][from_y] + 1;
            vis[to_x][to_y] = true;
            q.emplace(to_x, to_y);
        }
    };

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

        // left
        if (x != 1 || y != 1) {
            int l_x, l_y;
            if (y == 1) {
                l_x = x - 1;
                l_y = l[x - 1];
            } else {
                l_x = x;
                l_y = y - 1;
            }
            visit(l_x, l_y, x, y);
        }

        // right
        if (x != n || y != 1) {
            int r_x, r_y;
            if (y == l[x]) {
                r_x = x + 1;
                r_y = 1;
            } else {
                r_x = x;
                r_y = y + 1;
            }
            visit(r_x, r_y, x, y);
        }

        // up
        if (x != 1) {
            visit(x - 1, min(y, l[x - 1]), x, y);
        }

        // down
        if (x != n) {
            visit(x + 1, min(y, l[x + 1]), x, y);
        }
    }
    cout << dist[end.first][end.second];
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    if (n <= 1000) subtask_1_2(n);
}
#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...