TopCoder

User's AC Ratio

95.0% (19/20)

Submission's AC Ratio

44.4% (32/72)

Description

請找出在 8-puzzle遊戲中,從初始盤面至最終盤面最少需要移動的方格數。每一個方格一次只能移至相鄰的空格中。例如在下面的圖例中,從初始盤面至最終盤面最少需要移動 4個方格。


 1 2 3    1 2 3     1 2 3    1 2 3    1 2 3
 4 8 5    4 8 5     4 0 5    4 5 0    4 5 6
 7 6 0    7 0 6     7 8 6    7 8 6    7 8 0

初始盤面   第一步結果   第二步結果   第三步結果  第四步結果(最終盤面)

Input Format

輸入檔內容有兩列,各為9個數字(0~8)的數串,相鄰的兩個數字之間以一個空格分開。這些數字依序代表一個盤面「由左而右」、「由上至下」的狀態,其中 0 代表空格。第一列數串所代表的是初始盤面,而第二列數串代表的是最終盤面。

Output Format

請輸出從初始盤面至最終盤面所需移動的最少方格數。

Sample Input

1 2 3 4 8 5 7 6 0
1 2 3 4 5 6 7 8 0

Sample Output

4

Hints

Problem Source

原TIOJ1198 / TOI2004初選(prob 4)。

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536