d001. Jumping Array Puzzle 來了 - 花中程式設計挑戰系統

Content

有一個比 8-puzzle 與 15-puzzle 還要簡單的遊戲，名字叫做 Jumping Array Puzzle。

玩的棋盤只有一個橫列，每次玩的時候會有一個初始盤面。

舉例來說，假設有一個初始盤面是 102 ， 0 代表沒有棋子，另外兩個位置分別為1與2兩個棋子。

棋子的種類總共有 1~9 種，分別就用 1~9 編號代表。

每次移動的時候，玩家可以選擇四種狀況：

{左移一格，右移一格，左跳一格，或是右跳一格}，只要棋子想要移動的地方是空白即可。

給定一個初始盤面與目標盤面，請找出從初始盤面到目標盤面所需要最少的移動次數?

舉例來說，初始盤面是 102 目標盤面是 201

1右移一格 012

2左跳一格 210

1右移一格 201

最少需要三步可以達到目標盤面，輸出便為 3。

Input

每筆測試資料會有兩行由0~9的數字組成的盤面，分別為初始盤面與目標盤面，例如：

盤面的長度為 n ，其中 3 ≤ n ≤ 30

102

201

Output

請輸出一個數字，代表最少可以達到目標盤面的步數

Sample Input

123101111
111101321

Sample Output

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (15%): 1.0s , <1K
不公開測資點#1 (15%): 2.0s , <1K
不公開測資點#2 (25%): 3.0s , <1K
不公開測資點#3 (15%): 2.0s , <1K
不公開測資點#4 (30%): 3.0s , <1K

Hint ：

Tags:

A* BFS IDS

出處:

[管理者：

zero (管理員)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」

有一個 比 8-puzzle 與 15-puzzle 還要簡單的遊戲，名字叫做 Jumping Array Puzzle。