d207. 10181 - 15 - Puzzle - 高中生程式解題系統

內容

15-puzzle 是一個廣受歡迎的遊戲，就算你光從字面上可能不知道 15-puzzle 是什麼，但是你一定看過。
這遊戲是由 15 個可滑動的方塊組合成的，分別標上 1 ~ 15 的數字，然後擺在一個 4 x 4 大小的框架中， ( 當然有一個格子是空的 ) 。

這個遊戲的目的就是將所有方塊移動成如下的樣子：

在這裡，合乎規則的動作便是將空白格和其上下左右 ( 如果沒有超出框架 ) 的方塊交換位置。


一個隨機的盤面。	將空格向右移。

將空格向上移。	將空格向左移。

如果這個盤面無解，請輸出一行 This puzzle is not solvable.

輸入說明

第一行有一個正整數 T 代表以下有 T 組測資，

每組測資為 4 x 4 的方陣，由 0 ~ 15 組成，其中 0 代表 puzzle 的空格。

輸出說明

對每組測資，輸出一行。

若有解的話，請出輸出最少要幾步才能將起始盤面變換成目標盤面。

若無解，請輸出 This puzzle is not solvable.

注意：本題答案有可能超過 50 步，和 Uva 之要求不盡相同。

範例輸入 #1

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

範例輸出 #1

9
This puzzle is not solvable.

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (50%): 3.0s , <1K
公開測資點#1 (50%): 3.0s , <1K

提示：

先玩玩哈電族的華容道吧!

標籤:

哈電族 - 華容道

出處:

UVa 10181 [管理者： VacationClub (雄中公假社) ]

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