【牛客】[编程题]跳石板-白红宇的个人博客

【牛客】[编程题]跳石板

发布日期：2021-05-10 06:33:39 浏览次数：16 分类：精选文章

本文共 1543 字，大约阅读时间需要 5 分钟。

小易来到了一条石板路前，每块石板依次编号为1、2、3…。为了前进，小易必须从当前石板编号为K的位置跳到K+X的位置，其中X是K的约数（不含1和K本身）。具体来说，X必须是K的因数，且大于1，小于K。例如，当K=4时，X只能为2，因为4的因数是1、2、4，其中X不能为1和4自身。

目标是从编号为N的石板跳到编号为M的石板，找出最少需要跳跃的次数。

方法思路

为了找到最少跳跃次数，可以使用广度优先搜索（BFS）算法。BFS适合这种最短路径问题，可以保证找到最小的跳跃次数。

步骤如下：

初始化一个数组 vec，用于记录到达每个位置的最小跳跃次数。将所有位置初始化为一个很大的值（表示无法到达），并将起点N设置为0，因为起点不需要跳跃。

使用一个队列来处理每个石板位置。队列中的元素表示当前要处理的位置。

从起点N开始，遍历所有可能的下一个位置。对于当前位置K，找到所有可能的因数X（不包括1和K本身），并计算下一个位置 target = K + X。

如果目标位置小于等于M，并且目前记录的到达次数比已记录的要少，则更新记录，并将目标位置加入队列。

重复上述步骤，直到找到目标位置M，或者队列处理完毕。

最终，检查 vec[M] 的值。如果值仍然是无穷大，则说明无法到达目标位置M；否则，输出该值。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int main() {    int N, M;    while (cin >> N >> M) {        vector
       
         vec(M + 1, INT_MAX);        vec[N] = 0;        queue
        
          q; q.push(N); while (!q.empty()) { int current = q.front(); q.pop(); // 找到current的所有合法的X for (int x = 2; x < current; ++x) { if (current % x == 0) { int target = current + x; if (target <= M) { if (vec[target] > vec[current] + 1) { vec[target] = vec[current] + 1; q.push(target); } } } } } if (vec[M] == INT_MAX) { cout << -1 << endl; } else { cout << vec[M] << endl; } } return 0;}

代码说明

读取输入：代码开始部分读取输入的N和M，确保它们是整数。

初始化数组vec：大小为M+1，初始化为INT_MAX，表示无法到达。起点N的位置跳跃次数设置为0。

队列初始化：使用队列来处理石板位置，确保先进先处理。

循环处理每个位置：从队列中取出当前位置current，然后遍历current的所有可能因数X（不包括1和本身）。

计算下一个位置target：根据X的值，计算下一个位置。如果该位置未被访问过，或者能以更少的步骤到达，则更新记录，并将目标位置加入队列。

输出结果：在处理完所有位置后，检查目标位置M的跳跃次数。如果还是INT_MAX，输出-1；否则，输出跳跃次数。

该代码使用广度优先搜索，确保找到从N到M的最短跳跃次数。

上一篇：【网易邮箱】换绑安全手机（①之前的手机号注销了怎么办 ②网易人工客服在哪）

下一篇：【Linux】读写锁

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！