【正经题解】空间转移

广搜

#include <iostream>
#include <queue>
#include <algorithm>  // 添加这行头文件以使用 min 函数

using namespace std;

const int MAX_LENGTH = 10001;
int arrayLength, start, target;  // 将 end 改成 target
int steps[MAX_LENGTH], minSteps = MAX_LENGTH, visited[MAX_LENGTH];

struct Node {
    int position, stepCount;
};

// 判断位置是否在数组范围内
bool inArrayBounds(int pos) {
    return pos >= 1 and pos <= arrayLength;
}

// 广度优先搜索
void breadthFirstSearch() {
    queue<Node> q;
    q.push({start, 0});

    while (!q.empty()) {
        Node s = q.front();
        q.pop();

        int currentPos = s.position, currentSteps = s.stepCount;

        // 到达目标位置
        if (currentPos == target) {
            minSteps = min(minSteps, currentSteps);
            return;
        }

        int nextPos1 = currentPos + steps[currentPos];
        int nextPos2 = currentPos - steps[currentPos];

        // 扩展下一步可能的位置
        if (inArrayBounds(nextPos1) and !visited[nextPos1]) {
            q.push({nextPos1, currentSteps + 1});
            visited[nextPos1] = 1;
        }
        if (inArrayBounds(nextPos2) and !visited[nextPos2]) {
            q.push({nextPos2, currentSteps + 1});
            visited[nextPos2] = 1;
        }
    }
    return;
}

int main() {
    // 输入数组长度、起始位置和目标位置
    cin >> arrayLength >> start >> target;  // 将 end 改成 target

    // 输入每一步的距离
    for (int i = 1; i <= arrayLength; i++) {
        cin >> steps[i];
    }

    // 执行广度优先搜索
    breadthFirstSearch();

    // 输出最小步数或-1（如果无法到达）
    if (minSteps == MAX_LENGTH) {
        cout << -1;
    } else {
        cout << minSteps;
    }

    return 0;
}