1573 . 數字盤遊戲(Puzzle)
TopCoder
Tags
Description
15-Puzzle是一個很適合打發時間的遊戲。
十六片石板整齊地排列成四行四列，現在拿掉一片石板後，在任意且不重複地在剩下的每塊石板上填入1到15之間的整數。
遊戲開始以後，每一步都可以將一片在空格旁邊的石板移到空格當中。
遊戲的目標就是要把這些石板經過上述操作整齊地排列成1到15，並且空格的位置出現在右下角。
現在給你一個遊戲開始時的盤面，請問最少要移動多少步才能夠達到最終目標？
Input Format
輸入包含四行四列，一共十六個數字，代表初始盤面。其中0的位置代表空格所在。
保證輸入的盤面若可達成最終目標，則答案不超過50。
Output Format
請輸出一個整數，代表達成目標所需操作的最少步數。如果無法達成最終目標，請輸出-1。
Sample Input 1
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
5 6 7 8
9 10 0 11
13 14 15 12
Sample Output 1
2
Sample Input 2
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0
5 6 7 8
9 10 11 12
13 15 14 0
Sample Output 2
-1
Hints
至少有30%的測試資料答案$\leq 5$。
Problem Source
原TIOJ1573 / 97建中校內資訊能力競賽(prob4)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |