蓝桥杯跳蚱蜢（bfs）

本文主要是介绍蓝桥杯跳蚱蜢（bfs），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 问题描述：

如图所示： 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。 请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？ 
输出
输出一个整数表示答案 

来源：http://oj.ecustacm.cn/problem.php?id=1318

2. 思路分析：

分析题目可以知道我们已知一个初始的盘面状态，需要求解到达目标盘面状态的最少步数，根据这个原状态到目标状态的最少步数的特点可知可以使用bfs（宽度优先搜索解决），bfs可以求解出到达目标状态的最少步数，可以规定原状态为"012345678"，目标状态为"087654321"，将状态设置为str字符串类型这样可以直接比较原状态与目标状态是否相等。当前状态可以交换从当前0的位置算起的左右两边的第一个元素与第二个元素的位置，可以通过下图来理解具体的过程

3. 代码如下：

import collections


def insertQueue(queue: collections.deque, dir: int, poll: tuple, vis: set):
    pos = poll[1]  # 0元素的位置
    status = poll[0]
    # 因为题目中的状态是滚动的所以需要通过对9取余实现滚动
    insertPos = (pos + dir + 9) % 9
    # 将字符串转为列表才可以交换元素, 然后再通过join方法将列表中的元素转为字符串
    t = list(status)
    t[pos], t[insertPos] = t[insertPos], t[pos]
    addStatus = "".join(t)
    if addStatus not in vis:
        vis.add(addStatus)
        queue.append((addStatus, insertPos, poll[2] + 1))


if __name__ == '__main__':
    # 因为求解的是最少的步数, 所以可以使用广度优先搜索解决
    queue = collections.deque()
    # 第一个参数为初始状态, 第二个参数是空盘子的位置, 第三个参数为到达当前状态的步数
    queue.append(("012345678", 0, 0))
    # 标记列表
    vis = set()
    vis.add("012345678")
    while queue:
        poll = queue.popleft()
        # 到达了目标状态那么输出最少步数即可
        if poll[0] == "087654321":
            print(poll[2])
            break
        # 可以向左边或者是右边跳一个或者是两个位置
        insertQueue(queue, -2, poll, vis)
        insertQueue(queue, -1, poll, vis)
        insertQueue(queue, 1, poll, vis)
        insertQueue(queue, 2, poll, vis)

这篇关于蓝桥杯跳蚱蜢（bfs）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！