题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下图所示： 有 9 只盘子，排成 1 个圆圈。 其中 88 只盘子内装着 88 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。
每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1-8 换位，2-7换位,...），至少要经过多少次跳跃？
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
思路：
如果让数字跳的话，情况太多，不容易编码，我们在这里让空盘子跳。将每次跳跃化简为空盘子与他相邻或者相隔一个的盘子交换位置。每次跳跃都可变化出四个新的排序，使用set()进行判重，如果已经搜索过当前的数字排序，则不需要继续搜索当前排序及其扩展的子排序。
在具体实现过程过，我们使用广度优先搜索，一层一层往下搜索，如果当前层出现了“087654321”，则当前层的层数为我们所求的跳跃最小次数
在代码中，我们假设空盘子是0，使用元组存储数据，格式为：
（当前排序，0的位置，最少跳几次）
代码
1. def insertQueue(q:list,dir:int,news:tuple,vis:set): 2. pos=news[1] #0的位置 3. status=news[0] #当前的字符串 4. insertPos=(pos+dir+9) % 9 #交换的位置 5. t=list(status) 6. t[pos],t[insertPos]=t[insertPos],t[pos] 7. addstatus="".join(t) 8. if addstatus not in vis: 9. vis.add(addstatus) 10. q.append((addstatus,insertPos,news[2]+1)) 11. 12. 13. 14. q=[("012345678",0,0)] 15. vis=set() 16. vis.add("012345678") 17. while q: 18. news=q.pop(0) 19. if news[0]=="087654321": 20. print(news[2]) 21. break 22. insertQueue(q,-2,news,vis) 23. insertQueue(q,-1,news,vis) 24. insertQueue(q,2,news,vis) 25. insertQueue(q,1,news,vis)
