跳跃机器人(Jumping Robot) 题解

思路分析

将 $1 \sim n$ 每个格子视为图中的顶点，从 $x$ 向合法（在 $[1, n]$ 范围内）的 $x - 1, x + 1, 2x$ 连边权为 $1$ 的有向边。从起点 $1$ 开始执行广度优先搜索（BFS），首次到达 $n$ 时的层数即为最少跳跃次数。注意不能跳到 $> n$ 的位置再减 $1$。时间复杂度 $O(n)$。

参考代码

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

const int MX = 1000005;
int distArr[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    for (int i = 1; i <= n; ++i) distArr[i] = -1;
    queue<int> q;
    distArr[1] = 0;
    q.push(1);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        if (x == n)
        {
            cout << distArr[x] << "\n";
            return 0;
        }
        int nxts[3] = {x - 1, x + 1, x * 2};
        for (int i = 0; i < 3; ++i)
        {
            int y = nxts[i];
            if (y >= 1 && y <= n && distArr[y] == -1)
            {
                distArr[y] = distArr[x] + 1;
                q.push(y);
            }
        }
    }
    return 0;
}