题目描述
本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。
如下图所示: 有 9只盘子,排成1个圆圈。 其中8只盘子内装着8只蚱蜢,有一个是空盘。 我们把这些蚱蜢顺时针编号为1~ 8。
每只蚱蜢都可以跳到相邻的空盘中, 也可以再用点力,越过一个相邻的蚱蜢跳到空盘中。
请你计算一下,如果要使得蚱蜢们的队形改为按照逆时针排列, 并且保持空盘的位置不变(也就是1−8换位,2−7换位,...),至少要经过多少次跳跃?
解决
1.乍一看这个题目很乱,每次跳的过程所有的蚱蜢都在跳,可以换一个角度,假设只有盘子在动,将圆圈划归为一个队列进行解决。
2.由此便可以将问题转化成盘子在队列中为0,初始状态为:“012345678”,通过跳一个或两个盘子向前(指的是0与8相连,因为一开始是圆圈)或向后跳,每次跳有4种选择,最终达到的状态为“087654321”。
3.在上述过程中存在重复的情况,可以使用集合set来判重
4.使用双端队列deque来解决,速度最快,同理可用list和Queue
from collections import deque # 引入双端队列
def insertQueue(q:deque,dir:int,now:tuple,vis:set):
# dir:跳的方向及步数 now:目前的状态,空盘子的位置,总共跳的次数 vis:出现过的状态
pos=now[1];status=now[0];insertPos=(pos+dir+9)%9
# pos:当前空盘子的位置 status:当前状态 insertPos:要跳到的下一处的位置
t=list(status) # 转换为列表
t[pos],t[insertPos]=t[insertPos],t[pos]
addStatus="".join(t)
if addStatus not in vis:
vis.add(addStatus)
q.append((addStatus,insertPos,now[2]+1))
q=deque()
q.append(("012345678",0,0)) # 初始状态,空盘子在0处,跳的次数为0
vis = set()
vis.add("012345678")
while q:
now = q.popleft()
if now[0]=="087654321":
print(now[2])
break
insertQueue(q,-2,now,vis)
insertQueue(q,2,now,vis)
insertQueue(q,-1,now,vis)
insertQueue(q,1,now,vis)
标签:python,insertQueue,pos,蓝桥,vis,蚱蜢,盘子,now
From: https://blog.csdn.net/iipphsjsj/article/details/145018806