前言
能加入到这届的青训营我十分的开心，更希望自己不仅能通过这次的青训营之旅丰富自己的阅历之余，还能够认识到更多的学习伙伴。最后通过快乐写码分享讲解我创作灵感和过程的同时，也希望大家可以及时纠正我的错误，伴我学习。
任务介绍
小青要找小码去玩，他们的家在一条直线上，当前小青在地点 N ，小码在地点 K （0≤N , K≤100 000），并且小码在自己家原地不动等待小青。小青有两种交通方式可选：步行和公交。 步行：小青可以在一分钟内从任意节点 X 移动到节点 X-1 或 X+1 公交：小青可以在一分钟内从任意节点 X 移动到节点 2×X （公交不可以向后走）
请帮助小青通知小码，小青最快到达时间是多久？ 输入： 两个整数 N 和 K 输出： 小青到小码家所需的最短时间（以分钟为单位）
任务分析
通过对题目的解读，不难看出这是一个求从起点N到终点K的最短路径的问题，可以使用宽度优先搜索算法BFS进行解题。
宽度优先搜索算法的搜索步骤一般是：
（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。
（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。
（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。
任务设计
假设小青起点N为节点N，并使用一个双端队列来实现宽度优先搜索算法，接着使用一个set来记录已经访问过的节点，这样就可以避免重复访问已经访问过的节点，由此来提高效率。
在这里，我假设小青和小码的位置关系为 N < K，代码中的边界条件也是基于此假设而设置的。如果你需要处理 N > K 的情况，需要对代码进行相应的修改。
另外，在这个问题中，如果起点和终点之间不存在路径，则返回 -1。
最后，这段代码的复杂度为 O(K)，因为只需要遍历K个节点即可找到终点，并且由于使用了set来判重，所以不存在重复便利相同节点的情况。
from collections import deque def shortest_path(N, K): queue = deque([(N, 0)]) visited = set() while queue: node, step = queue.popleft() if node == K: return step if node not in visited: visited.add(node) if node - 1 >= 0: queue.append((node - 1, step + 1)) if node + 1 <= K: queue.append((node + 1, step + 1)) if node * 2 <= K: queue.append((node * 2, step + 1)) return -1 if __name__ == '__main__': n, k = map(int, input("请输入小青和小码的位置:").split()) print("最短时间是：",shortest_path(n, k),"分钟")
总结
通过这次的解题，我认为这道题目也可以使用递归来实现宽度优先搜索算法，每一层的递归可以看作为一层的BFS，但考虑到递归是一种比较耗费时间的算法，对于量较大的数据，可能会导致超时，所以我暂时没用尝试使用递归进行解题。
写文章不易，如果你觉得文章对你有帮助，麻烦点一下点赞、收藏，你的支持是我写文章的最大动力！
最后，希望通过这次的讲解创作灵感和过程，能让掘友们看到对于这个主题的不一样的解法，也希望掘友们可以及时纠正我的错误。
