n140.
p12. 雙洞推盤遊戲
內容
雙洞推盤（two-hole puzzle）遊戲據說起源於台師大資工系，在 $\text{2021}$ 年起風行於台灣。本題考量解題時間，將盤面固定為 $4\times 4$，且其中最上兩排的 $8$ 個單格由左而右、由上而下，依序填入 $1$ 到 $8$ 的 $8$ 個數字，接下來剩下的單格隨機填入 $9$ 到 $14$ 的數字，而留下兩個空的單格(稱為雙洞），形成起始狀態，而空的單格可以由相鄰的上、下、左或右方有數字的單格移入其數字。雙洞推盤問題研究如何找出數字移入空格的最少步數的方式，藉以達成最後由上而下、由左而右，依序由 $1$ 到 $14$ 排序的目標狀態。舉下圖為例，由某個起始盤面至終點盤面，一個走最少步數的範例如下：
| |
請你寫一程式來求出最佳的走法，也就是走最少步數的走法。注意：我們給定的起始盤面一定會有解。
輸入說明
輸入共有 $4$ 行，每行各有 $4$ 個整數，表示起始盤面。其中前兩行的 $8$ 個數字依序為 $1$ 到 $8$，接下來兩行的 $8$ 個數字為 $9$ 到 $14$ 及兩個 $0$，形成起始狀態。注意：給定的初始盤面一定會有解。
輸出說明
對於每筆測試資料請輸出一個數字，表示最佳解的步數。
範例輸入
#1
1 2 3 4 5 6 7 8 13 9 0 11 0 10 14 12
範例輸出
#1
6
範例輸入
#2
1 2 3 4 5 6 7 8 0 9 11 0 13 10 14 12
範例輸出
#2
4
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <1K
公開 測資點#13 (5%): 2.0s , <1K
公開 測資點#14 (5%): 2.0s , <1K
公開 測資點#15 (5%): 2.0s , <1K
公開 測資點#16 (5%): 2.0s , <1K
公開 測資點#17 (5%): 2.0s , <1K
公開 測資點#18 (5%): 2.0s , <1K
公開 測資點#19 (5%): 2.0s , <1K
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1K
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <1K
公開 測資點#13 (5%): 2.0s , <1K
公開 測資點#14 (5%): 2.0s , <1K
公開 測資點#15 (5%): 2.0s , <1K
公開 測資點#16 (5%): 2.0s , <1K
公開 測資點#17 (5%): 2.0s , <1K
公開 測資點#18 (5%): 2.0s , <1K
公開 測資點#19 (5%): 2.0s , <1K
提示 ：
出處:
110新北市資訊學科能力複賽
[管理者：
liaoweichen1
...
(M_SQRT)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||