TopCoder

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

User's AC Ratio

64.7% (11/17)

Submission's AC Ratio

27.6% (32/116)

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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1
1 10000 65536 262144 2
2 10000 65536 262144 3
3 10000 65536 262144 4
4 10000 65536 262144 5
5 10000 65536 262144 6
6 10000 65536 262144 7
7 10000 65536 262144 8
8 10000 65536 262144 9
9 10000 65536 262144 10