文字教学

这道题是求最短路径的经典问题，用BFS（广度优先搜索）解决，因为BFS第一次到达目标位置时的步数就是最少跳跃次数：

1. 状态记录：用 dist[x] 表示到达第 x 个格子的最少步数，初始化为 -1（未访问），起点 dist[1] = 0。
2. BFS队列：从起点 1 开始入队，每次取出队首位置 x，生成三个可能的跳跃位置：x-1、x+1、2x。
3. 扩展规则：对每个新位置，检查是否在 [1,n] 范围内且未被访问过，若是则更新步数并入队。
4. 终止条件：当取出的位置是 n 时，直接输出当前步数，即为答案。

代码

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

const int N = 1e6 + 10;
int dist[N];
queue<int> q;

int main() {
    int n;
    cin >> n;
    memset(dist, -1, sizeof(dist));
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (x == n) {
            cout << dist[x] << endl;
            return 0;
        }
        int nx;
        // 跳x-1
        nx = x - 1;
        if (nx >= 1 && dist[nx] == -1) {
            dist[nx] = dist[x] + 1;
            q.push(nx);
        }
        // 跳x+1
        nx = x + 1;
        if (nx <= n && dist[nx] == -1) {
            dist[nx] = dist[x] + 1;
            q.push(nx);
        }
        // 跳2x
        nx = 2 * x;
        if (nx <= n && dist[nx] == -1) {
            dist[nx] = dist[x] + 1;
            q.push(nx);
        }
    }
    return 0;
}