蓝桥杯真题跳蚱蜢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 not q.empty():
    p = q.get()
    a = p[0]
    level = p[1]
    if a == end:
        print(level)#搜索次数，就是我们要的结果
        break
    pos = 0
    while a[pos] != '0':
        pos += 1
    posi = [i for i in range(4)]
    # 这是我们跳的四步，1， 2， -1， -2
    posi[0] = (pos + 8) % 9
    posi[1] = (pos + 1) % 9
    posi[2] = (pos + 7) % 9
    posi[3] = (pos + 2) % 9
    for 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

本文地址：https://blog.csdn.net/qq_51718832/article/details/114002842