欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

蓝桥杯真题跳蚱蜢python解答

程序员文章站 2022-05-14 16:40:05
题目如下:如图 p1.png 所示: 有9只盘子,排成1个圆圈。其中8只盘子内装着8只蚱蜢,有一个是空盘。我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中,也可以再用点力,越过一个相邻的蚱蜢跳到空盘中。请你计算一下,如果要使得蚱蜢们的队形改为按照逆时针排列,并且保持空盘的位置不变(也就是1-8换位,2-7换位,…),至少要经过多少次跳跃?注意:要求提交的是一个整数,请不要填写任何多余内容或说明文字。题目解答看到题目后,我们标记空的地方为0,就是要求我们从012345678...

题目如下:

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

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

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

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

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

注意:要求提交的是一个整数,请不要填写任何多余内容或说明文字。
蓝桥杯真题跳蚱蜢python解答

题目解答

看到题目后,我们标记空的地方为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

相关标签: 经验分享 python