[C++]洛谷B3626 跳跃机器人(题干 + 详细讲解, BFS练习题)

题干

题目描述

地上有一排格子，共n个位置。机器猫站在第一个格子上，需要取第n个格子里的东西。
机器猫当然不愿意自己跑过去，所以机器猫从口袋里掏出了一个机器人！这个机器人的行动遵循下面的规则：
初始时，机器人位于1号格子, 若机器人目前在x格子，那么它可以跳跃到x + 1, x - 1, 2 * x里的一个格子（不允许跳出界）
问机器人最少需要多少次跳跃，才能到达n号格子。

输入格式

第1行, 一个正整数n

输出格式

一行, 一个正整数, 表示最小跳跃次数.

输入输出样例

样例1

input输入:

30

expected output期望输出:

6

样例2

input输入:

50

expected output期望输出:

7

样例3

input输入:

64

expected output期望输出:

6

样例4

input输入:

63

expected output期望输出:

8

数据范围

对于100%的数据，有 1≤n≤1000000。

知识点提示

需要运用以下知识点:

• C++基础语法
• 简单的bfs广度优先搜索思想及代码实现能力
• 对于queue队列或vector向量等的了解与灵活运用

拥有以上知识点的掌握之后, 你可以尝试做出这道题.

AC代码与解析

解析请看注释

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

// 定义全局变量
int n;                // 存储目标数字
bool vis[1000005];    // 访问标记数组，记录数字是否已被访问过
int dis[1000005];     // 距离数组，记录从1到当前数字的最短步数

// 广度优先搜索函数，计算从1到n的最短步数
int bfs(){
    queue<int> q;     // 创建队列用于BFS
    q.push(1);        // 初始状态：数字1入队
    vis[1] = true;    // 标记数字1已访问
    dis[1] = 0;       // 数字1到自身的距离为0
    
    while(!q.empty()){  // 当队列不为空时循环
        int x = q.front();  // 取出队首元素
        if(x == n) return dis[x];  // 如果找到目标数字，返回当前步数
        q.pop();            // 弹出队首元素
        
        // 尝试三种操作：减1、加1、乘2
        
        // 操作1：数字减1
        int y = x - 1;
        if(0 <= y && y <= n && !vis[y]){  // 检查数字是否有效且未被访问
            vis[y] = true;          // 标记已访问
            dis[y] = dis[x] + 1;    // 更新步数
            q.push(y);              // 入队
        }
        
        // 操作2：数字加1
        y = x + 1;
        if(0 <= y && y <= n && !vis[y]){  // 检查数字是否有效且未被访问
            vis[y] = true;          // 标记已访问
            dis[y] = dis[x] + 1;    // 更新步数
            q.push(y);              // 入队
        }
        
        // 操作3：数字乘2
        y = x * 2;
        if(0 <= y && y <= n && !vis[y]){  // 检查数字是否有效且未被访问
            vis[y] = true;          // 标记已访问
            dis[y] = dis[x] + 1;    // 更新步数
            q.push(y);              // 入队
        }
    }
    return -1;  // 如果无法到达目标数字，返回-1
}

int main(){
    cin >> n;            // 输入目标数字
    cout << bfs() << endl;  // 调用广度优先搜索并输出结果
    return 0;
}