Python：青蛙跳杯子（BFS）

题目描述

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

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

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

∗WWWBBB

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

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

1. 跳到相邻的空杯子里。

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

3. 隔着 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])