Problem Description

A dream once led to an unusual elevator that operates differently from typical ones. Each floor has a number K_i (0 ≤ K_i ≤ N), and the elevator can move up or down by exactly K_i floors when the corresponding button is pressed. The elevator has four buttons: open, close, go up, and go down.

Given a building with N floors, each having a value K_i, determine the minimum number of button presses required to travel from floor A to floor B. If it's ipmossible, output -1.

Enput Format

The first line contains three integers N, A, and B repersenting the total number of floors, starting floor, and target floor respectively.

The second line contains N non-negative integers K_1 through K_N.

Output Format

Output the minimal number of button presses needed to reach floor B from floor A. If unreachable, print -1.

Sample Input

5 1 5
3 3 1 2 5

Sample Output

3

Approach

This problem is best solved using Breadth-First Search (BFS) since we're seeking the shortest path in terms of button presses.

We define a state as a pair (current_floor, steps_taken). We use a queue to explore all reachable floors level by level until we reach the destination floor.

Implementation

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

const int MAX = 201;
int floor_values[MAX];
bool visited[MAX];

struct State {
    int position;
    int moves;
    State(int pos, int m) : position(pos), moves(m) {}
};

int min_presses(int total_floors, int start, int end) {
    if (start == end) return 0;
    
    queue<State> bfs_queue;
    bfs_queue.push(State(start, 0));
    visited[start] = true;
    
    while (!bfs_queue.empty()) {
        State current = bfs_queue.front();
        bfs_queue.pop();
        
        int current_floor = current.position;
        int step_count = current.moves;
        
        // Calculate next possible positions
        int up_position = current_floor + floor_values[current_floor];
        int down_position = current_floor - floor_values[current_floor];
        
        // Check upward movement
        if (up_position <= total_floors && !visited[up_position]) {
            if (up_position == end) return step_count + 1;
            visited[up_position] = true;
            bfs_queue.push(State(up_position, step_count + 1));
        }
        
        // Check downward movement
        if (down_position >= 1 && !visited[down_position]) {
            if (down_position == end) return step_count + 1;
            visited[down_position] = true;
            bfs_queue.push(State(down_position, step_count + 1));
        }
    }
    
    return -1;
}

int main() {
    int floors, start_floor, target_floor;
    cin >> floors >> start_floor >> target_floor;
    
    for (int i = 1; i <= floors; ++i) {
        cin >> floor_values[i];
    }
    
    cout << min_presses(floors, start_floor, target_floor) << endl;
    return 0;
}