Python：青蛙跳杯子（BFS）
题目描述
X 星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
X 星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
∗WWWBBB
其中，W 字母表示白色青蛙，B 表示黑色青蛙，∗ 表示空杯子。
X 星的青蛙很有些癖好，它们只做 3 个动作之一：
-
跳到相邻的空杯子里。
-
隔着 1 只其它的青蛙（随便什么颜色）跳到空杯子里。
-
隔着 2 只其它的青蛙（随便什么颜色）跳到空杯子里。
对于上图的局面，只要 1 步，就可跳成下图局面：
WWW∗BBB
本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
输入描述
输入为 2 行，2 个串，表示初始局面和目标局面。我们约定，输入的串的长度不超过 15。
输出描述
输出要求为一个整数，表示至少需要多少步的青蛙跳。
输入输出样例
示例
输入
*WWBB
WWBB*
输出
2思路：
当前状态可能的变化状态：
1、左\右移一个格到 空格位置
2、左\右移两个格到 空格位置
3、左\右移三个格到 空格位置
任务要求是从初始状态到目标状态最短路径（最少跳动次数）
搜索跳动一次所有的可能结果，并保存所以可能性作为下次搜索的初始状态。
参考代码：
import sys
chushi = input()
mubiao = input()
lis = [1,-1,2,-2,3,-3]
experience = {chushi} #标记状态
queue= [[chushi,0]] #状态和层数
while queue: #若不为空old = queue.pop(0) #弹出第一个元素for i in lis:state = list(old[0]) #字符串转化为列表step = old[1]kgwz = state.index('*') #查找空格位置xkgwz = kgwz + i #新空格位置if 0<=xkgwz<len(chushi): #判断新空格位置是否出界state[kgwz] = state[xkgwz]state[xkgwz] = '*'new_state = "".join(state)step += 1if new_state == mubiao:print(step)sys.exit(0) #程序终止if new_state not in experience: #若新状态没有出现过以前的状态中experience.add(new_state)queue.append([new_state,step])