[Python 3]魔法数字 - BFS

根据题意, 数字 n 的三种可能转化方式: n -> n - 1 or n + 1 or n * n
因此, 可从n开始进行广度优先搜索, 记录当前数字 curNum 以及当前的操作步数 curStep, 并使用一个 set 记录已访问过的数字, 将curNum - 1, curNum + 1, curNum * curNum中未被访问的数字添加到搜索队列. 当curNum == m时搜索结束, 返回此时的操作步数, 即为所求的最少步数(因为步数是不断 +1 的, 可看作在所有边权值均为1的图上, 从n到m的最短距离)
[注] 由于n -> n + 1以及n -> n * n这两种转化方式的存在, n会越来越大甚至超过m, 因此需要进行一次"剪枝": n不超过m时, 才能进行上述转化.

#
# 返回最后要输出的答案
# @param n int整型 表示牛牛的数字
# @param m int整型 表示牛妹的数字
# @return int整型
#
class Solution:
    def solve(self , n , m ):
        que = [[n, 0]]
        seen = set(); seen.add(n)
        while que:
            curNum, curStep = que.pop(0)
            if curNum == m:
                return curStep
            if curNum - 1 not in seen:
                que.append([curNum - 1, curStep + 1])
                seen.add(curNum - 1)
            if curNum <= m and (curNum + 1 not in seen):
                que.append([curNum + 1, curStep + 1])
                seen.add(curNum + 1)
            if curNum <= m and (curNum * curNum not in seen):
                que.append([curNum * curNum, curStep + 1])
                seen.add(curNum * curNum)
        return -1