蓝桥杯精选赛题——跳蚱蜢

蚱蜢"/>

蓝桥杯精选赛题——跳蚱蜢

已收录此专栏。
前一讲我们已经学习了BFS，并且通过一个题来进行了编程。
我们今天讲的跳蚱蜢这个题目，也是运用了BFS算法。
BFS 的题目，很多与判重有关。BFS 的原理是逐步扩展下一层，把扩展出的下一层点放进队列中处理。在任意时刻，队列中只包含相邻两层的点。理解不了这句话的话，我们不妨想一想全球气候这道题，或许你就可以理解了。

题目描述

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

图片描述

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

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

输入描述

无

输出描述

无

解题思路及详细答案

直接让蚱蜢跳到空盘有点麻烦，因为有很多蚱蜢在跳，跳晕了。但如果反过来看，让空盘跳，跳到蚱蜢的位置，就简单多了，只有一个空盘在跳。
是不是感觉这种也有点绕，我们再来引入一个建模大法：“化圆为线”！把空盘看成 0，那么有 9 个数字{ 0,1,2,3,4,5,6,7,8}，一个圆圈上的 9 个数字，拉直成了一条线上的 9​ 个数字。于是就可以将题目转换为八数码问题，而八数码是经典的BFS问题。
什么是八数码呢？
八数码有 9 个数字{ 0,1,2,3,4,5,6,7,8}，它有 9!=362880种排列，也不算多。本题的初始状态是“012345678”，终止状态是“087654321”。从初始状态跳一次，有4种情况：
所以用 BFS 扩展每一层。每一层就是蚱蜢跳了一次，扩展到某一层时发现了终点“087654321”，那么这一层的深度就是蚱蜢跳跃的次数。
但是这道题只用BFS是不够的。
你想，第 1 步到第 2 步，有 4 种跳法；第 2 步到第 3 步，有 4×4 种;⋯；第 2020 步，有4²⁰ = 1万亿种！太多了！BFS 的队列肯定放不下呀!
那怎么办呢？
**判重大法！**判断有没有重复跳，如果跳到一个曾经出现过的情况，就不用往下跳了。一共只有 9!=362880 种情况，好判。再来分析一下代码复杂度：在每一层，能扩展出最少 4 种、最多 362880 种情况。最后算出的答案是在 20 层时到达了终点，那么最多算20×362880=7257600次。

答案

def insertQueue(q: list, dir: int, news: tuple, vis: set):pos = news[1]   # 0的位置status = news[0]insertPos = (pos + dir + 9) % 9# 将字符串转为列表比较好处理t = list(status)t[pos], t[insertPos] = t[insertPos], t[pos]addStatus = "".join(t)if addStatus not in vis:vis.add(addStatus)q.append((addStatus, insertPos, news[2] + 1))# main
q = [("012345678", 0, 0)]
vis = set()
vis.add("012345678")
while q:news = q.pop(0)       if news[0] == "087654321":    # 到达了目标状态输出最少步数print(news[2])breakinsertQueue(q, -2, news, vis)   #扩展下一层的4种情况insertQueue(q, -1, news, vis)insertQueue(q, 1, news, vis)insertQueue(q, 2, news, vis)