一维数轴最短路

题目描述

给定一个一维数轴上的起点 s 和终点 t。

从当前位置 x 出发，每次可以进行下面三种操作之一：

• x -> x + 1
• x -> x - 1
• x -> x * 2

请你求出从 s 到 t 至少需要多少步。

输入格式

一行两个整数 s,t，表示起点和终点。

输出格式

输出一个整数，表示从 s 到 t 的最少步数。

输入输出样例 #1

输入 #1

5 17

输出 #1

4

样例解释

一种最短走法是：

5 -> 10 -> 9 -> 18 -> 17

一共需要 4 步。

数据范围

0 <= s,t <= 100000

提示

本题可以使用 BFS。把每个数字看成一个状态，每次从当前状态扩展到 x - 1、x + 1、x * 2。第一次到达终点时的层数就是最少步数。