笔试时间：2025年5月17日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：迷幻森林

dd被困在了一个迷幻森林，现在她面前有一条凶险的大河，河中央有n个神奇的浮块，浮块按1~n顺序标号，但两两并不相接，第i个浮块上有一个数字a[i]，可能是正数，也可能是负数，每块浮块都附带一个魔法结果用于传送，当a[i]为正数时，dd可以选择传送到第i+k（1≤k≤a[i]）个浮块上，当dd抵达n号浮块时才可以顺利脱身，显然不管a[n]是多少，都没有任何意义，当a[i]为负时，dd只能选择标号小于等于i+a[i]的任意一块浮块进行传送，当i+a[i]＜1时，默认只能传送到1的位置，每次传送都会花费1s的时间，随着时间的流逝，迷雾森林的空气会被逐渐榨干，她现在在1号浮块，她想知道，她最快多久能顺利脱身，如果始终无法逃脱，请输出-1。

输入描述

第一行一个数n(2≤n≤2000)

接下来一行n个数ai表示浮块上的数字

输出描述

输出一行，表示对应的答案。

样例输入

4  

2 2 -1 2

样例输出

2

说明：

1跳到2，1s  

2跳到4，1s  

共2s

参考题解

每个节点i可以传送到其他节点，具体取决于a[i]的值： 如果a[i]为正，可以从i传送到i+1到i+a[i]的任意节点。 如果a[i]为负，可以从i传送到1到i+a[i]的任意节点（如果i+a[i] < 1，则只能传送到1）。 广度优先搜索（BFS）：由于每次传送的代价相同（1秒），BFS适合用来寻找最短路径。我们从节点1开始，逐层探索可以到达的节点，直到到达节点n或无法继续前进。 队列和访问标记：使用队列来管理当前层的节点，并用一个数组记录到达每个节点的最短时间，避免重复处理。

C++：

// C++ 版本
#include <bits/stdc++.h>
using namespace std;

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

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

    vector<int> visited(n+1, -1);
    deque<int> q;
    q.push_back(1);
    visited[1] = 0;
    bool found = false;

    while (!q.empty()) {
        int cur = q.front();
        q.pop_front();
        if (cur == n) {
            found = true;
            break;
        }
        int jump = a[cur];
        if (jump > 0) {
            // 向前跳
            for (int nxt = cur + 1; nxt <= min(n, cur + jump); nxt++) {
                if (visited[nxt] == -1) {
                    visited[nxt] = visited[cur] + 1;
                    q.push_back(nxt);
                }
            }
        } else {
            // 向后跳
            for (int nxt = max(1, cur + jump); nxt < cur; nxt++) {
                if (visited[nxt] == -1) {
                    visited[nxt] = visited[cur] + 1;
                    q.push_back(nxt);
                }
            }
        }
    }

    cout << (found ? visited[n] : -1) << "\n";
    return 0;
}

Java：

// Java 版本
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        int[] a = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int[] visited = new int[n+1];
        Arrays.fill(visited, -1);
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(1);
        visited[1] = 0;
        boolean found = false;

        while (!queue.isEmpty()) {
            int cur = queue.removeFirst();
            if (cur == n) {
                found = true;
                break;
            }
            int jump = a[cur];
            if (jump > 0) {
                // 向前跳
                for (int nxt = cur + 1; nxt <= Math.min(n, cur + jump); nxt++) {
                    if (visited[nxt] == -1) {
                        visited[nxt] = visited[cur] + 1;
                        queue.addLast(nxt);
                    }
                }
            } else {
                // 向后跳
                for (int nxt = Math.max(1, cur + jump); nxt < cur; nxt++) {
                    if (visited[nxt] == -1) {
                        visited[nxt] = visited[cur] + 1;
                        queue.addLast(nxt);
                    }
                }
            }