题意
-
从数轴上某一点移动一次,可以有三个选择:向前走一步,移动到 x + 1, 向后走一步,移动到 x - 1,向前跳一跳,跳到 2 * x
-
问:给定一个起点和终点,最好移动多少次,可以从起点移动到终点。
题解
考察 bfs 知识点。
-
从起点开始,用 bfs 爆搜走到其他所有点的移动次数。
-
需要将走到过的点记录下来,因为同一个点可以被多种方式走到,我们只保留步数最少的方法(也就是第一次走到的方法)。
-
如果搜到了终点,就停止 bfs, 输出结果。
# bfs 需要队列
from collections import deque
# 接收起点和终点
s, e = map(int, input().split())
#初始 bfs 化队列
q = deque()
# 保存起点到其他点的最少移动次数
dist = dict()
def bfs():
# 初始化 bfs 队列
q.append(s)
# 初始化起点距离
dist[s] = 0
while q:
# 取队头
x = q.popleft()
# 如果是终点,则返回移动次数
if x == e:
return dist[x]
# 从 x 移动一次能到达的三个点坐标
next_x = [x + 1, x - 1, x + x]
# 从 x 一次向三个点移动
for nx in next_x:
# 如果目标点没有到达过,并且在题目要求范围内,则移动
if nx not in dist and 0 <= nx <= 10**5:
# 移动到目标点的次数是移动到当前点的次数+1
dist[nx] = dist[x] + 1
# 目标点放入队列
q.append(nx)
print(bfs())
附上C++代码:
谢谢哥们