1198 . 8-puzzle

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

90.5% (86/95)

Submission's AC Ratio

43.5% (202/464)

Tags

TOI TOI-pre 2004-TOI-pre

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

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

Sample Output 1

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 (VSS, 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
Submit
Back to Top