C++算法: 数轴上的最小移动次数

问题描述

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

算法思路

这个问题可以使用递归和回溯的思想来解决。从起点A开始，每次可以向左或向右移动k_i步，并递归地探索每个可达的位置。为了避免重复计算，可以使用一个数组记录每个位置是否已经被访问过。当到达终点B时，记录移动的次数。最后，比较所有可行路径的移动次数，找到最小值即为答案。

C++代码实现cpp#include #include using namespace std;

int minMoves(int n, int a, int b, vector& k, vector& visited) { if (a == b) { return 0; // 已到达终点，不需要移动 }

if (a < 1 || a > n || visited[a] || k[a] == 0) {        return -1; // 当前位置不可达或无法移动    }

visited[a] = true; // 标记当前位置已访问

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

int leftMoves = minMoves(n, left, b, k, visited);    int rightMoves = minMoves(n, right, b, k, visited);

visited[a] = false; // 回溯，重置当前位置为未访问

if (leftMoves == -1 && rightMoves == -1) {        return -1; // 左右都无法到达终点    } else if (leftMoves == -1) {        return rightMoves + 1; // 只能向右移动    } else if (rightMoves == -1) {        return leftMoves + 1; // 只能向左移动    } else {        return min(leftMoves, rightMoves) + 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];    }

vector<bool> visited(n + 1, false);    int result = minMoves(n, a, b, k, visited);    cout << result << endl;

return 0;}

代码解释

minMoves函数：使用递归和回溯查找从位置a到位置b的最小移动次数。 - 参数： - n：数轴长度 - a：当前位置 - b：目标位置 - k：存储每个位置可移动距离的数组 - visited：记录每个位置是否被访问过的数组 - 返回值： - 如果能到达终点，返回最小移动次数 - 否则返回-1- main函数：读取输入数据，调用minMoves函数计算最小移动次数，并输出结果。

复杂度分析

该算法的时间复杂度为O(2^n)，空间复杂度为O(n)，其中n为数轴长度。

总结

本文介绍了如何使用递归和回溯的思想解决数轴上的最小移动次数问题，并提供了C++代码实现。需要注意的是，该算法在最坏情况下时间复杂度较高，对于规模较大的问题可能需要考虑更高效的算法。