B3626 跳跃机器人 題解

ShanCreeperPro · 2022-04-23 19:11:15 · 题解

B3626 跳跃机器人 題解

前言：

一定要标记！一定要标记，否则会 MLE。

找别人调代码，结果：

这题我们可以使用 bfs。

题目大意： 有 n 个格子，从第一个开始每次只能移动到 x+1 或 x-1 或 2 \times x 的地方，问到达 n 要几步。

这题可以使用 bfs 解决。

由于 bfs 是向外扩张的，一个点被初次访问是在第 k 层的话，则可以走 k 步到这个点。

bfs 写法如下：

• 定义结构体 pos，里面存储格子坐标 x 和需要花费的步数 cost，并在里面设定一个构造函数：

struct pos{
    int x,cost;
    pos(int ax,int acost){
        x=ax,cost=acost;
    }
};

• 定义队列 q，先将 (1,0) 压入队列；
• 如果队列非空：
  • 取出队首；
  • 判断是否合法：如果越界或已经访问过则非法；
  • 若合法，标记为 1；
  • 如果走到 n，输出方案数 cost；
  • 将 (x+1,cost+1),(x-1,cost+1),(2*x,cost+1) 入队。

简单的说就是：初始化、处理非法、判断是否到达、扩展。

管理员注：

由于课程需要本题不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】