蓝桥杯 跳蚱蜢

蚱蜢"/>

蓝桥杯 跳蚱蜢

如下图所示： 有 99 只盘子，排成 11 个圆圈。 其中 88 只盘子内装着 88 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 11 ~ 88。

图片描述

每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1-81−8 换位，2-72−7换位,…），至少要经过多少次跳跃？

重点就是遍历每个点可以走的位置然后在寻找可以移动的点然后在遍历直到找到满足的位置的步数，得让这样会重复计算很多超过递归深度，所以要动态规划，避免重复计算。
代码如下：

#判断是否满足要求
def isGo(item):count=8isgo=Truefor i in item:if not item[i]==count and item[i]!=None:isgo=Falsecount-=1if item[len(item)]!=None:isgo=Falsereturn isgo#寻找点
def fund(item):golist=[]count=0n=len(item)for i in item:if item[i]==None:count=ibreakif count ==n:golist.append(1)golist.append(count-1)golist.append(count - 2)golist.append(2)elif  count==1:golist.append(count+2)golist.append(n)golist.append(count-1)golist.append(count+1)elif  count==8:golist.append(count-1)golist.append(n)golist.append(1)golist.append(count-2)elif  count==2:golist.append(count+2)golist.append(n)golist.append(1)golist.append(count+1)else:golist.append(count + 2)golist.append(count+1)golist.append(count-1)golist.append(count + 1)return [count,golist]def dsf(data,isTrue,x,y):global allsglobal countisTrue=isGo(data)#判断是否已经满足移动要求满足就是True不满足结束falseif data in alls:#判断是不是已经计算过，避免重复returnif isTrue:#结束判断returnelse:if x!=None and y!=None:#第一次调x，y为空不需要调换位置或者添加到判重的数组alls.append(data.copy())temp=data[y]data[x]=tempdata[y]=Nonecount+=1item= fund(data)#寻找可以和None交换位置的点for goy in item[1]:#便利这些点dsf(data,isTrue,item[0],goy,)if __name__=='__main__':alls=[]#存储已经移动过的数组，如果存在这个数组里面就说明不需要在进行计算    count=0#对步数进行计数datadict={1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:None}#开始位置dsf(datadict,False,None,None)#递归方法第一个参数就是所在位置的字典，# 第二个判断是否结束，第三是为None的位置，第三个是向空移动的蚂蚱print(count)