数轴移动问题：C++代码实现最短移动次数

问题描述:

有一个长度为n的数轴，每个点有一个数字'ki'表示该点可以向左或向右移动'ki'个位置。规定移动后的点不能大于n也不能小于1。现给定点A、B，问从A点到B点至少要移动多少次？

输入:

第一行输入三个整型数，n，a，b分别表示数轴长度，A点位置，B点位置第二行输入n个非负整数，表示'ki'

输出:

如果能够到达输出次数，否则输出-1；

样例输入:

5 1 5
3 3 1 2 5

样例输出:

C++代码:

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

int minMoves(int n, int a, int b, vector<int>& k) {
    vector<int> dist(n + 1, -1); // 初始化距离数组，-1表示未访问过
    queue<int> q;
    q.push(a); // 将起点入队
    dist[a] = 0; // 起点距离为0

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        if (curr == b) {
            return dist[curr]; // 已到达终点，返回最小移动次数
        }

        int left = curr - k[curr];
        int right = curr + k[curr];

        if (left >= 1 && dist[left] == -1) {
            q.push(left); // 向左移动
            dist[left] = dist[curr] + 1;
        }

        if (right <= n && dist[right] == -1) {
            q.push(right); // 向右移动
            dist[right] = dist[curr] + 1;
        }
    }

    return -1; // 无法到达终点
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;

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

    int result = minMoves(n, a, b, k);
    cout << result << endl;

    return 0;
}

代码解释:

使用广度优先搜索 (BFS) 算法来找到从起点 A 到终点 B 的最短路径。
dist 数组记录每个点到起点的最小移动次数。
使用队列 q 来存储待访问的点。
从起点 A 开始，将 A 入队并设置 dist[a] = 0。
循环遍历队列，取出队头元素 curr。
判断 curr 是否为终点 B，如果是则返回 dist[curr] 作为最小移动次数。
计算 curr 向左移动和向右移动的位置 left 和 right。
如果 left 和 right 在数轴范围内且未访问过，则将它们入队并更新 dist 数组。
如果循环结束后仍未找到终点 B，则返回 -1 表示无法到达。

运行代码:

输入样例数据，可以得到输出结果 3。

总结:

这篇文章介绍了一个数轴移动问题，并使用 C++ 代码实现了最短移动次数的计算。代码使用广度优先搜索算法，简洁高效地解决了问题。希望这篇文章能帮助你理解和解决类似的算法问题。