TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (10/15)

Submission's AC Ratio

27.6% (29/105)

Description

15-Puzzle是一個很適合打發時間的遊戲。

十六片石板整齊地排列成四行四列,現在拿掉一片石板後,在任意且不重複地在剩下的每塊石板上填入1到15之間的整數。

遊戲開始以後,每一步都可以將一片在空格旁邊的石板移到空格當中。

遊戲的目標就是要把這些石板經過上述操作整齊地排列成1到15,並且空格的位置出現在右下角。

現在給你一個遊戲開始時的盤面,請問最少要移動多少步才能夠達到最終目標?

Input Format

輸入包含四行四列,一共十六個數字,代表初始盤面。其中0的位置代表空格所在。

保證輸入的盤面若可達成最終目標,則答案不超過50。

Output Format

請輸出一個整數,代表達成目標所需操作的最少步數。如果無法達成最終目標,請輸出-1。

Sample Input

Sample Input 1
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12

Sample Input 2
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 0

Sample Output

Sample Output 1
2

Sample Output 2
-1

Hints

至少有30%的測試資料答案$\leq 5$。

Problem Source

原TIOJ1573 / 97建中校內資訊能力競賽(prob4)

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144
3 10000 65536 262144
4 10000 65536 262144
5 10000 65536 262144
6 10000 65536 262144
7 10000 65536 262144
8 10000 65536 262144
9 10000 65536 262144