蓝桥杯真题跳蚱蜢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换位,…),至少要经过多少次跳跃?
注意:要求提交的是一个整数,请不要填写任何多余内容或说明文字。
题目解答
看到题目后,我们标记空的地方为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