TopCoder

Thumb 100
西瓜
いつか、私を助けてね

User's AC Ratio

92.9% (39/42)

Submission's AC Ratio

53.3% (96/180)

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

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6