邱縣網(wǎng)站建設(shè)今日國內(nèi)新聞大事20條
題目描述
X?星球的流行寵物是青蛙，一般有兩種顏色：白色和黑色。
X?星球的居民喜歡把它們放在一排茶杯里，這樣可以觀察它們跳來跳去。
如下圖，有一排杯子，左邊的一個(gè)是空著的，右邊的杯子，每個(gè)里邊有一只青蛙。
?WWWBBB
其中，W?字母表示白色青蛙，B?表示黑色青蛙，??表示空杯子。
X?星的青蛙很有些癖好，它們只做 3 個(gè)動(dòng)作之一：
-
跳到相鄰的空杯子里。
-
隔著 1 只其它的青蛙（隨便什么顏色）跳到空杯子里。
-
隔著 2 只其它的青蛙（隨便什么顏色）跳到空杯子里。
對(duì)于上圖的局面，只要 1 步，就可跳成下圖局面：
WWW?BBB
本題的任務(wù)就是已知初始局面，詢問至少需要幾步，才能跳成另一個(gè)目標(biāo)局面。
輸入描述
輸入為 2 行，2 個(gè)串，表示初始局面和目標(biāo)局面。我們約定，輸入的串的長度不超過 15。
輸出描述
輸出要求為一個(gè)整數(shù)，表示至少需要多少步的青蛙跳。
輸入輸出樣例
示例
輸入
*WWBB
WWBB*
輸出
2?思路：
當(dāng)前狀態(tài)可能的變化狀態(tài)：
????????1、左\右移一個(gè)格到 空格位置
????????2、左\右移兩個(gè)格到 空格位置
????????3、左\右移三個(gè)格到 空格位置
任務(wù)要求是從初始狀態(tài)到目標(biāo)狀態(tài)最短路徑（最少跳動(dòng)次數(shù)）
搜索跳動(dòng)一次所有的可能結(jié)果，并保存所以可能性作為下次搜索的初始狀態(tài)。
參考代碼：
import sys
chushi = input()
mubiao = input()
lis = [1,-1,2,-2,3,-3]
experience = {chushi} #標(biāo)記狀態(tài)
queue= [[chushi,0]] #狀態(tài)和層數(shù)
while queue: #若不為空old = queue.pop(0) #彈出第一個(gè)元素for i in lis:state = list(old[0]) #字符串轉(zhuǎn)化為列表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: #若新狀態(tài)沒有出現(xiàn)過以前的狀態(tài)中experience.add(new_state)queue.append([new_state,step])