蓝桥杯真题跳蚱蜢python解答

蓝桥杯真题跳蚱蜢python解答

题目如下：

如图 p1.png 所示： 有9只盘子，排成1个圆圈。

其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。

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

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

注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

题目解答

看到题目后，我们标记空的地方为0，就是要求我们从012345678转化为087654321，要用空格作为跳跃点，我们就要知道0的位置，跳跃方式有四种，我们采用广度优先搜索进行解决。

import queue
start = '012345678'
end = '087654321'
q = queue.Queue()
q.put([start, 0])
s = set()
s.add(start)
while pty():p = q.get()a = p[0]level = p[1]if a == end:print(level)#搜索次数，就是我们要的结果breakpos = 0while a[pos] != '0':pos += 1posi = [i for i in range(4)]# 这是我们跳的四步，1， 2， -1， -2posi[0] = (pos + 8) % 9posi[1] = (pos + 1) % 9posi[2] = (pos + 7) % 9posi[3] = (pos + 2) % 9for i in range(4):b = list(a)#遍历四次就是广度搜索以下b[pos] = b[posi[i]]b[posi[i]] = '0'b = ''.join(b)if not b in s:#我们还要去重s.add(b)q.put([b, level+1])

答案：20