最近入了一款游戲 chronicon,?類暗黑2, 像素畫(huà)風(fēng)?游戲性還行。其中有一個(gè)小游戲：有9個(gè)由3個(gè)三種顏色組成的3X3矩形，需要使每一行的顏色相同(如圖1)，玩家可通過(guò)周圍的12個(gè)按鈕來(lái)改變順序。點(diǎn)擊靠近按鈕的那一行或列即可把這一行或者列所有的顏色往按鈕方向移動(dòng)一格,最頂端的顏色會(huì)移動(dòng)至最末尾，規(guī)則就是這樣。

為了找到解決此問(wèn)題的最短步驟，我使用了BFS、兩處棧(其實(shí)只需一個(gè)隊(duì)列)、一個(gè)隊(duì)列 。

首先要找到最短步驟，顯然BFS很適用此問(wèn)題，一共12個(gè)按鈕，實(shí)際生效的按鈕其實(shí)只有6個(gè)（因?yàn)榱砹鶄€(gè)只是反著過(guò)來(lái)，實(shí)際效果就是對(duì)應(yīng)按鈕按下n-1次的效果）,所以只需對(duì)6個(gè)按鈕做BFS即可,這里我們?nèi)∽蠛蜕线@6個(gè)按鈕.?

BFS策略:每次讀取隊(duì)列首部,判斷此時(shí)的狀態(tài)是否是游戲成功,

• 如果未成功,對(duì)此時(shí)的6個(gè)按鈕做枚舉,如果按下后的狀態(tài)沒(méi)有記錄過(guò),則依次入隊(duì),并記錄入隊(duì)的顏色狀態(tài)

• 如果成功,則跳出BFS,此時(shí)的結(jié)果就是我們想要的結(jié)果.這里給出部分代碼:

  這里ki=0 ki<3 ki++?而不是6, 是因?yàn)槲矣昧藘蓚€(gè)for分別枚舉的行和列

至此我們已經(jīng)知道能否找到最短步驟解，但還需要增加一些邏輯來(lái)給出最短步驟的每一步。

在存顏色信息的數(shù)據(jù)結(jié)構(gòu)中增加一個(gè)std::stack記為msta,表示至此顏色,已經(jīng)經(jīng)過(guò)的按鈕按下步驟的記錄

然后每當(dāng)找到一個(gè)未記錄過(guò)的顏色信息,就把BFS隊(duì)列首部的msta加入此時(shí)的按鈕編號(hào).這樣最后得到的顏色信息中就記錄了所有的按鈕按下順序.

最后還有一步,就是顯示按鈕按下順序,由于我們是用棧存儲(chǔ)的記錄,最后的一次按鈕記錄在棧頂,所以需要聲明另一個(gè)棧,然后依次把棧頂出棧,出棧元素入棧到另一個(gè)棧中,這樣另一個(gè)棧再依次出棧,得到的結(jié)果就是順序的了!

總結(jié):雖然3x3比較簡(jiǎn)單,可以總結(jié)經(jīng)驗(yàn)來(lái)解決,但是如果給一個(gè)10x10下的此問(wèn)題就很棘手了.用程序來(lái)解決,不用動(dòng)腦子,也可以鍛煉自己的能力(雖然我10分鐘就有正確的思路了(逃