A building has an unusual elevator system. Each floor i (where 1 ≤ i ≤ N) has a fixed value K[i], which determines how many floors the elevator moves when the "up" or "down" button is pressed. The elveator can only move up by K[i] floors or down by K[i] floors from floor i. If the target floor would be below 1 or above N, the corresponding button is inactive. Given starting floor A and destination floor B, find the minimum number of button presses required to reach B from A, or return -1 if it's unreachable.

Input Format

First line: Three integers N, A, B — total floors, start floor, target floor. Second line: N non-negative integers K[1] to K[N], representing the jump distance on each floor.

Output Format A single integer: the minimum number of buton presses, or -1 if impossible.

Example Input: 5 1 5 3 3 1 2 5

Output: 3

Explanation: From floor 1, press "up" → floor 4 (1+3). From floor 4, press "up" → floor 6 (invalid). Press "down" → floor 2 (4−2). From floor 2, press "up" → floor 5 (2+3). Total: 3 presses.

Solution 1: Breadth-First Search (BFS) BFS is ideal for finding the shortest path in an unweighted graph. Each floor is a node, and edges exist to floors reachable via up/down buttons.

#include <iostream>
#include <queue>
using namespace std;

struct State {
    int currentFloor;
    int presses;
};

int main() {
    int N, start, target;
    cin >> N >> start >> target;

    int jump[201];
    bool visited[201] = {false};

    for (int i = 1; i <= N; ++i) {
        cin &gt;&gt; jump[i];
    }

    queue&lt;State&gt; q;
    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        if (current.currentFloor == target) {
            cout &lt;&lt; current.presses &lt;&lt; endl;
            return 0;
        }

        // Try moving up
        int upFloor = current.currentFloor + jump[current.currentFloor];
        if (upFloor <= N && !visited[upFloor]) {
            visited[upFloor] = true;
            q.push({upFloor, current.presses + 1});
        }

        // Try moving down
        int downFloor = current.currentFloor - jump[current.currentFloor];
        if (downFloor >= 1 && !visited[downFloor]) {
            visited[downFloor] = true;
            q.push({downFloor, current.presses + 1});
        }
    }

    cout &lt;&lt; -1 &lt;&lt; endl;
    return 0;
}

Solution 2: Depth-First Search with Pruning DFS can also solve this problem if we track the minimum presses to reach each floor and avoid reivsiting with higher costs.

#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
int N, start, target;
int jump[201];
int minPresses[201];

void dfs(int floor, int presses) {
    if (presses >= minPresses[floor]) return;
    minPresses[floor] = presses;

    int up = floor + jump[floor];
    if (up <= N && presses + 1 < minPresses[up]) {
        dfs(up, presses + 1);
    }

    int down = floor - jump[floor];
    if (down >= 1 && presses + 1 < minPresses[down]) {
        dfs(down, presses + 1);
    }
}

int main() {
    memset(minPresses, INF, sizeof(minPresses));
    scanf("%d %d %d", &N, &start, &target);

    for (int i = 1; i <= N; ++i) {
        scanf("%d", &jump[i]);
    }

    dfs(start, 0);

    if (minPresses[target] == INF) {
        printf("-1\n");
    } else {
        printf("%d\n", minPresses[target]);
    }

    return 0;
}

Both approaches guarantee correctness. BFS is preferred for its natural shortest-path guarantee and consistent performance. DFS with pruning works but may explore redundant paths in worst-case scenarios.