移動字母
2x3=6個方格中放入ABCDE五個字母,右下角的那個格空著。如圖所示
和空格子相鄰的格子中的字母可以移動到空格中,比如,圖中的C和E就可以移動,移動後的局面分別是:
A B
D E C
A B C
D E
為了表示方便,我們把6個格子中字母配置用一個串表示出來,比如上邊的兩種局面分別表示為:
AB*DEC
ABCD*E
題目的要求是:請編寫程序,由用戶輸入若干表示局面的串,程序通過計算,輸出是否能通過對初始狀態經過若干次移動到達該狀態。可以實現輸出1,否則輸出0。初始狀態為:ABCDE*
用戶輸入的格式是:先是一個整數n,表示接下來有n行狀態。程序輸出也應該是n行1或0
例如,用戶輸入:/p>
3
ABCDE*
AB*DEC
CAED*B
則程序應該輸出:
1
1
0
--------------------------------------------------------------------------------------------------------------------------------
可以這樣看,字母的移動與唯一的“空格”的移動具是等效的。
我們可以考慮空格的移動,這樣更簡便。
由初始狀態開始,移動空格後,形成新的狀態。不斷地增加新的狀態,直到包含了所有的可能狀態。
也可以遞歸的想法:
由初始狀態一步就可以達到的狀態判為有解;
否則,由衍生狀態繼續遞歸求解。
為防止無限期地調用下去,必須考慮結束遞歸的條件。比如:考慮遞歸深度不能超過總的格子的數目