自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:01，当前版本为作者最后更新于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)$ 入队。

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

管理员注：

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

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