【蓝桥杯】43692.青蛙跳杯子

题目描述

X 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。

X 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。

如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。

$\ast WWWBBB$

其中，
W 字母表示白色青蛙，
B 表示黑色青蛙，
∗ 表示空杯子。

X 星的青蛙很有些癖好，它们只做 3 个动作之一：

跳到相邻的空杯子里。

隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。

隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。

对于上图的局面，只要 1 步，就可跳成下图局面：

$WWW\ast BBB$

本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。

输入描述

输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。

输出描述

输出要求为一个整数，表示至少需要多少步的青蛙跳。

输入输出样例

示例
输入

※WWBB
WWBB※

输出

2

解题思路

先来看看 $\ast WWWBBB$ 怎么变成 $WWW\ast BBB$ 。
很简单，第三个 W 的青蛙向左跳了2格，占了 $\ast$ 的位置，而跳走后，原来的位置变为 $\ast$ 。

再看看 $\ast WWBB$ 怎么变为 $WWBB\ast$
至少需要两步: $\ast WWBB$ → $WW\ast BB$ → $WWBB\ast$

对于已知初始状态和结束状态的题目，简单粗暴的解题思路无非两种，一种枚举，一种遍历，把所有的可能性都试一遍，而找出其中 路径最短 / 步骤最少 的，无疑要使用遍历算法，那么优先考虑 广度优先BFS 或 深度优先DFS。

假设起始局面为 $\ast WWBB$，目标局面为 $WWBB\ast$。

1. 初始时，队列 Q = [[‘$\ast WWBB$’, 0]]，集合 aset = {‘$\ast WWBB$’}。
2. 从队列取出 [‘$\ast WWBB$’, 0]，对其应用各种移动方式：
     当移动方式为 1 时，得到新局面 $W\ast WBB$，步数变为 1。检查发现 $W\ast WBB$ 不在 aset 中，将其加入 aset 并把 [‘$W\ast WBB$’, 1] 加入队列 Q。
     类似地，依次应用其他移动方式生成新局面并处理。
3. 继续从队列中取出元素进行探索，直到找到目标局面 $WWBB\ast$，此时输出的步数即为从起始局面到目标局面的最少步数。

  通过这种逐层扩展搜索空间的方式，使用 广度优先搜索BFS 能够保证第一次找到目标状态时所经过的路径是最短的。

算法步骤

1. 读取用户输入的初始局面和目标局面。
2. 定义青蛙可能的移动方式。
3. 使用集合 aset 记录已经访问过的局面，避免重复搜索。
4. 初始化队列 Q，将初始局面和步数 0 加入队列。
5. 不断从队列中取出元素，尝试所有可能的移动方式，得到新的局面。
6. 如果新的局面等于目标局面，输出步数并结束搜索。
7. 如果新的局面未被访问过，将其加入已访问集合和队列，继续搜索。

代码展示

感谢 @朱恒彤 同学提供的代码。

import os
import sys

# 从用户输入中读取初始局面和目标局面，start 是起始状态，end 是目标状态
start = input()
end = input()

# 定义青蛙可能的移动方式
# 这是一个列表，表示在字符串中可以移动的位数（向右或向左），
# 其中正数表示向右移动，负数表示向左移动。例如，1 表示向右移动 1 格，-2 表示向左移动 2 格
move = [1, -1, 2, -2, 3, -3]

# aset 是一个集合，集合的特点是元素具有唯一性，用于记录已经访问过的状态，以避免重复访问。
# 初始时将起始状态加入集合
aset = {start}

# 定义广度优先搜索函数
def bfs():
    # 初始化队列，队列中的每个元素是一个列表，包含当前局面和到达该局面所需的步数
    # 初始时队列中只有一个元素，即起始状态和对应的步数 0，说明步数是从 0 开始的
    Q = [[start, 0]]

    # 当队列不为空时，继续搜索
    while Q:
        # 从队列中取出队首元素
        # 运用了 while Q 循环。只要 Q 不为空，就会从队列中取出一个 old
        # old 是一个列表，old[0] 是当前局面，old[1] 是到达该局面所需的步数
        old = Q.pop(0)

        # 遍历所有可能的移动方式
        for i in move:
            # 将当前局面的字符串转换为字符列表，因为字符串是不可变类型，而列表是可变类型，方便进行字符交换操作
            a = list(old[0])

            # 获取到达当前局面所需的步数
            b = old[1]

            # 找到空位（用 '*' 表示）在字符列表中的索引
            c = a.index('*')

            # 计算空位移动后的新索引
            d = c + i

            # 检查新索引是否在合法范围内
            if 0 <= d < len(start):
                # 交换空位和新索引位置的字符
                a[c] = a[d]
                # 将新的字符位置的值转移到 '*' 的位置，把原来 '*' 的位置设置为新的字符
                a[d] = '*'

                # 将字符列表转换回字符串，重新形成新的状态字符，得到新的局面
                e = ''.join(a)

                # 步数加 1
                b += 1

                # 如果新的局面等于目标局面，输出当前步数并结束搜索
                if e == end:
                    print(b)
                    return

                # 如果新的局面未被访问过，将其加入已访问集合aset，表示为已访问，并加入队列Q，，表示加入新的局面和对应的步数，然后继续搜索
                if e not in aset:
                    aset.add(e)
                    Q.append([e, b])

# 调用广度优先搜索函数开始搜索
bfs()