蓝桥杯—青蛙跳杯子（python、广度优先搜索）

    本文灵感来自八数码问题。参考八数码文章  https://www.cnblogs.com/heyjjjjj/p/13401364.html，一篇很优秀的文章。

问题描述
    X星球的流行宠物是青蛙，一般有两种颜色：白色和黑色。
    X星球的居民喜欢把它们放在一排茶杯里，这样可以观察它们跳来跳去。
    如下图，有一排杯子，左边的一个是空着的，右边的杯子，每个里边有一只青蛙。
    *WWWBBB

    其中，W字母表示白色青蛙，B表示黑色青蛙，*表示空杯子。
    X星的青蛙很有些癖好，它们只做3个动作之一：
    1. 跳到相邻的空杯子里。
    2. 隔着1只其它的青蛙（随便什么颜色）跳到空杯子里。
    3. 隔着2只其它的青蛙（随便什么颜色）跳到空杯子里。

    对于上图的局面，只要1步，就可跳成下图局面：
    WWW*BBB
    本题的任务就是已知初始局面，询问至少需要几步，才能跳成另一个目标局面。
    输入为2行，2个串，表示初始局面和目标局面。
    输出要求为一个整数，表示至少需要多少步的青蛙跳

样例输入
    $\ast$WWBB
    WWBB$\ast$
样例输出
    2
样例输入
    $\ast$WWBB
    WWBB$\ast$
样例输出
    10
数据规模和约定
    我们约定，输入的串的长度不超过15
思路
    把青蛙跳杯子的问题转换为杯子可以向左移动1、2、3个位置，向右移动1，2，3个位置，注意 * 在边缘时不可超出范围移动，这样，每种情况最多有六种可能，将问题转换为了广度优先搜索。将每种情况保存在open列表中，避免重复。建立一个评估函数，不在位数，不在位数是指若对于一个格子，他的对应位置的数不是目标数，则加一。我们优先趋向于处理评估函数值更小的那种方向。
    本文在处理字符串时，将W转换为1，B转换为2，$\ast$转换为0。
    注：本文在处理13个以上字符串时超出了规定时间，如果各位解决了该问题欢迎在评论区留言，这个问题网上没有找到用python编程的，博主实力不够。

#青蛙跳杯子

import copy

#保存结果
result = []

class status():
    # 以树的形式记录搜索
    # status是树的一个节点
    father=None

    def __init__(self,lst,evaluate,step):
        self.lst=lst               #记录当前状态
        self.evaluate=evaluate     #估价函数值
        self.step=step             #递归树的深度

    def point_father(self,f):
        self.father=f              #指向父节点

    def change_evaluate(self,e):
        self.evaluate=e            #更新估价函数值

def compute_count_unpos(lst,b):
    #不在位数
    count=0
    for i in range(len(lst)):
        if(lst[i]==0):
            continue
        if(lst[i]!=b.lst[i]):
            count+=1
    return count

def develop(now):
    #通过移动杯子位置，拓展现在的状态，生成移动后可能的状态并以列表形式返回
    out = []
    
    temp = copy.deepcopy(now.lst)
    for i in range(len(temp)):
        if(temp[i] == 0):
            pos = i
    
    #当长度为3
    if(len(temp) == 3):
        if(pos == 0):
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
        if(pos == 1):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
        if(pos == 2):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            
    #当长度为4
    if(len(temp) == 4):
        if(pos == 0):
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右三个
            temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
            out.append(temp)
        if(pos == 1):
             #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
        if(pos == 2):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
        if(pos == 3):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左三个
            temp[pos],temp[pos-3] = temp[pos-3],temp[pos]
            out.append(temp)
        
    #当长度为5
    if(len(temp) == 5):
        if(pos == 0):
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右三个
            temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
            out.append(temp)
        #如果在pos = 1,则向右移动一个、两个、或三个，向左移动一个
        if(pos == 1):
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右三个
            temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
        if(pos == 2):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
        if(pos == 3):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
        if(pos == 4):
             #向左一个
            templ[pos],templ[pos-1] = templ[pos-1],templ[pos]
            out.append(templ)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左三个
            temp[pos],temp[pos-3] = temp[pos-3],temp[pos]
            out.append(temp)
    #当长度大于5
    if(len(temp)>5):
        #如果在pos = 1,则向右移动一个、两个、或三个
        if(pos == 0):
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右三个
            temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
            out.append(temp)
        #如果在pos = 1,则向右移动一个、两个、或三个，向左移动一个
        if(pos == 1):
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右三个
            temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
        #如果在pos = 2,则向右移动一个、两个、或三个，向左移动一个、两个
        if(pos == 2):
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右三个
            temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
        

        
        #左右两边空间足够
        if (pos>2 and pos<(len(temp)-3)):
            for i in range(3,len(temp)-3):
                if pos == i:
                    #向右一个
                    temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
                    out.append(temp)
                    temp = copy.deepcopy(now.lst)
                    #向右两个
                    temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
                    out.append(temp)
                    temp = copy.deepcopy(now.lst)
                    #向右三个
                    temp[pos],temp[pos+3] = temp[pos+3],temp[pos]
                    out.append(temp)
                    temp = copy.deepcopy(now.lst)
                     #向左一个
                    temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
                    out.append(temp)
                    temp = copy.deepcopy(now.lst)
                    #向左两个
                    temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
                    out.append(temp)
                    temp = copy.deepcopy(now.lst)
                    #向左三个
                    temp[pos],temp[pos-3] = temp[pos-3],temp[pos]
                    out.append(temp)
            
        
        #如果在pos = len(lst)-3,则向右移动一个、两个，向左移动一个、两个、三个
        if(pos == len(temp)-3):
            #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向右两个
            temp[pos],temp[pos+2] = temp[pos+2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左三个
            temp[pos],temp[pos-3] = temp[pos-3],temp[pos]
            out.append(temp)
        #如果在pos = len(lst)-2,则向右移动一个，向左移动一个、两个、三个
        if(pos == len(temp)-2):
             #向右一个
            temp[pos],temp[pos+1] = temp[pos+1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左三个
            temp[pos],temp[pos-3] = temp[pos-3],temp[pos]
            out.append(temp)
        #如果在pos = len(lst)-1,向左移动一个、两个、三个
        if(pos == len(temp)-1):
            #向左一个
            temp[pos],temp[pos-1] = temp[pos-1],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左两个
            temp[pos],temp[pos-2] = temp[pos-2],temp[pos]
            out.append(temp)
            temp = copy.deepcopy(now.lst)
            #向左三个
            temp[pos],temp[pos-3] = temp[pos-3],temp[pos]
            out.append(temp)
    return out



def judge_exist(child,table):
    #判断child的list是否在table表中存在
    for i in range(len(table)):
        if(table[i].lst==child):
            return i
    return -1

def print_father(now):
    if(now.father==None):
        #print(now.lst,now.evaluate)
        return
    print_father(now.father)
    #print(now.lst,now.evaluate)
    result.append(now.lst)


def main(compute_evaluate):
    b = status(end,0,0)  #目标状态
    a=status(lst,compute_evaluate(lst,b)+0,0) # 得到节点a
    

    open=[a] # 初始化open表
    closed=[]

    flag=0
    step=0 # 深度初始化为0
    while(len(open)!=0):
        now=open[0]
        open.remove(now) #取出open表的首节点
        if(now.lst==b.lst): #如果他是目标状态，则结束
            #print("匹配成功！")
            print_father(now)
            flag=1
            break

        children=develop(now) #生成当前状态的后续状态
        if(len(children)==0): #无法生成，则取下个节点
            continue

        for child in children:
            if(judge_exist(child,open)==-1 and judge_exist(child,closed)==-1): #如果子状态不在open表或closed表
                evaluate=compute_evaluate(child,b)+now.step+1 #计算估价函数值
                node=status(child,evaluate,now.step+1) #成为新状态加入open表，深度+1
                node.point_father(now) #父节点指向now
                open.append(node)

            elif(judge_exist(child,open)!=-1): #如果已经在open表
                index=judge_exist(child,open) #得到子节点在open表的下标
                if(now.step+1<open[index].step): #如果是沿着更短的深度到达
                    open[index].step=now.step+1 #更新子节点的估价函数和深度和父节点
                    open[index].point_father(now)
                    open[index].change_evaluate(compute_evaluate(child,b)+now.step+1)

            elif(judge_exist(child,closed)!=-1): #如果已经在closed表
                index = judge_exist(child, closed) #得到子节点在closed表的下标
                if(now.step+1<closed[index].step): #如果是沿着更短的深度到达
                    temp=closed[index] #从closed表中移除
                    closed.remove(temp)
                    temp.step=now.step+1 #并重新加入open表中
                    temp.change_evaluate(compute_evaluate(child,b)+now.step+1)
                    temp.point_father(now)
                    open.append(temp)

        closed.append(now) #closed表移除当前已处理节点
        open.sort(key=lambda x:x.evaluate,reverse=False) #按照估价函数值排序open表，第一个元素估价函数值最高

    if(flag==0): #open表为空且未到达目标节点
        print("匹配失败！")
        
    print(len(result))    #输出步数


lst = str(input())
lst = [c.replace('W','1') for c in lst]  #转换字符
lst = [c.replace('B','2') for c in lst]
lst = [c.replace('*','0') for c in lst]
lst = [int(x) for x in lst]
end = str(input())
end = [c.replace('W','1') for c in end]
end = [c.replace('B','2') for c in end]
end = [c.replace('*','0') for c in end]
end = [int(x) for x in end]
main(compute_count_unpos)