这是一个典型的最短路径问题,可以使用广度优先搜索(BFS来解决。每个状态代表当前的数字,通过应用两种魔法可以到达下一个状态。我们需要找到从 1 到 b 的最短路径(由于状态只有1000000种)。也可以考虑记忆化搜索来做这一道题
1.初始化: 使用一个队列来进行 BFS,初始状态为 1,步数为 0。 使用一个数组 visited 来记录每个数字被访问的最少步数,初始时所有值为 -1(未访问)。
2.BFS 过程:
小红最近正在学习魔法,通过魔法可以改变纸上的数字。
小红一共会两种魔法,第一种魔法可以将纸上数字变为它的a倍,比如在a=3时,他可以将666变成1998;第二种魔法可以让纸上的数字循环右移一次,比如12345在施加第二种魔法后会变成51234,119会变911,需要注意的是,小红无法对小于10或是以0为结尾的数施加第二种魔法。
纸上的数字初始是1,小红想将它变成自己的幸运数字b,那么请问小红至少需要施加几次魔法。如果无论如何 都无法将它变成b,请输出−1。
输入一行,包含两个正整数a,b 2≤a,b<106
输出一行一个数,表示最少的魔法次数,或输出−1表示无解。
输入
3 621
输出
6
说明
样例解释1
一种可行的方法为:1−>3−>9−>27−>72−>216−>621
输入样例2
3 666
输出样例2
−1