题解 | 袋鼠过河

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

int main() {
    int n;
    cin >> n;
    
    vector<int> power(n);
    for(int i = 0; i < n; i++) {
        cin >> power[i];
    }
    
    vector<bool> visited(n + 1, false);  // 多一个位置表示跳出
    vector<int> dist(n + 1, -1);
    queue<int> q;
    
    // 从位置0开始
    q.push(0);
    visited[0] = true;
    dist[0] = 0;
    
    while(!q.empty()) {
        int curr = q.front();
        q.pop();
        
        // 如果当前位置是0，无法继续跳跃
        if(curr < n && power[curr] == 0) continue;
        
        // 从当前位置跳跃
        for(int step = 1; step <= (curr < n ? power[curr] : 0); step++) {
            int next = curr + step;
            if(next <= n && !visited[next]) {
                visited[next] = true;
                dist[next] = dist[curr] + 1;
                q.push(next);
            }
        }
    }
    
    cout << dist[n] << endl;  // 输出跳到n位置（跳出）的步数
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] power = new int[n];
        for(int i = 0; i < n; i++) {
            power[i] = sc.nextInt();
        }
        
        boolean[] visited = new boolean[n + 1];  // 多一个位置表示跳出
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        
        // 从位置0开始
        q.offer(0);
        visited[0] = true;
        dist[0] = 0;
        
        while(!q.isEmpty()) {
            int curr = q.poll();
            
            // 如果当前位置是0，无法继续跳跃
            if(curr < n && power[curr] == 0) continue;
            
            // 从当前位置跳跃
            for(int step = 1; step <= (curr < n ? power[curr] : 0); step++) {
                int next = curr + step;
                if(next <= n && !visited[next]) {
                    visited[next] = true;
                    dist[next] = dist[curr] + 1;
                    q.offer(next);
                }
            }
        }
        
        System.out.println(dist[n]);  // 输出跳到n位置（跳出）的步数
    }
}

from collections import deque

def solve():
    n = int(input())
    power = list(map(int, input().split()))
    
    visited = [False] * (n + 1)  # 多一个位置表示跳出
    dist = [-1] * (n + 1)
    q = deque()
    
    # 从位置0开始
    q.append(0)
    visited[0] = True
    dist[0] = 0
    
    while q:
        curr = q.popleft()
        
        # 如果当前位置是0，无法继续跳跃
        if curr < n and power[curr] == 0:
            continue
        
        # 从当前位置跳跃
        max_step = power[curr] if curr < n else 0
        for step in range(1, max_step + 1):
            next_pos = curr + step
            if next_pos <= n and not visited[next_pos]:
                visited[next_pos] = True
                dist[next_pos] = dist[curr] + 1
                q.append(next_pos)
    
    print(dist[n])  # 输出跳到n位置（跳出）的步数

if __name__ == "__main__":
    solve()