n140. p12. 雙洞推盤遊戲 - 高中生程式解題系統

內容

　　雙洞推盤（two-hole puzzle）遊戲據說起源於台師大資工系，在 $2021$ 年起風行於台灣。本題考量解題時間，將盤面固定為 $4 \times 4$ ，且其中最上兩排的 $8$ 個單格由左而右、由上而下，依序填入 $1$ 到 $8$ 的 $8$ 個數字，接下來剩下的單格隨機填入 $9$ 到 $14$ 的數字，而留下兩個空的單格(稱為雙洞），形成起始狀態，而空的單格可以由相鄰的上、下、左或右方有數字的單格移入其數字。雙洞推盤問題研究如何找出數字移入空格的最少步數的方式，藉以達成最後由上而下、由左而右，依序由 $1$ 到 $14$ 排序的目標狀態。舉下圖為例，由某個起始盤面至終點盤面，一個走最少步數的範例如下：

　　請你寫一程式來求出最佳的走法，也就是走最少步數的走法。注意：我們給定的起始盤面一定會有解。

輸入說明

　　輸入共有 $4$ 行，每行各有 $4$ 個整數，表示起始盤面。其中前兩行的 $8$ 個數字依序為 $1$ 到 $8$ ，接下來兩行的 $8$ 個數字為 $9$ 到 $14$ 及兩個 $0$ ，形成起始狀態。注意：給定的初始盤面一定會有解。

輸出說明

　　對於每筆測試資料請輸出一個數字，表示最佳解的步數。

範例輸入 #1

範例輸出 #1

範例輸入 #2

1 2 3 4
5 6 7 8
0 9 11 0
13 10 14 12

範例輸出 #2

測資資訊：

記憶體限制： 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

提示：

標籤:

BFS 模擬

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」