1673 . 旋轉遊戲
TopCoder
Tags
Description
小華（嘿不是小明了！）發明了一種遊戲叫做旋轉遊戲。
這不是那種常常在舞池看到那種兩三個人轉來轉去那種遊戲，這是一類益智遊戲。
一個旋轉遊戲的盤面如下，共有24格，其中1, 2, 3各剛好8個。
圖中顯示的A~H是這個旋轉遊戲的八種移動方式。
例如說A就是把該直行7個數字都往上推，同時最上面那個1就會遞補到最下面。
遊戲目標是讓任何一個數字八個都排在正中央的環上。例如右圖即是2-完成圖。
小華自己試玩了一下發現這個遊戲難度太高了，他便希望寫一個程式來幫他找出最小步數的答案，
若有許多一樣最小步數的解法，要找出字典順序最小的答案。
同時，他也想知道這個最佳解的中心是哪個數字。
Input Format
單一檔案含多組資料，每筆資料：
只有一行，包含24個數字以空白分隔，表示起始盤面。
起始盤面的給法是由上到下、由左到右依序給數字。
例如上圖左邊那個盤面會表示為1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
當讀到一行只含單一一個數字0表示輸入結束，請不要對這行作輸出。
Output Format
對每組詢問輸出兩行，
第一行包含一個字串表示最小步數中字典序最小的解。
如果當前盤面不需移動，請輸出"No moves needed"（不含雙引號）
第二行包含一個數字表示終止盤面的中心數字是多少。
Sample Input 1
1 1 1 1 3 2 3 2 3 1 3 2 2 3 1 2 2 2 3 1 2 1 3 3
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
1 1 1 1 3 3 2 2 2 3 3 2 2 3 3 2 2 2 3 3 1 1 1 1
0
1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
1 1 1 1 3 3 2 2 2 3 3 2 2 3 3 2 2 2 3 3 1 1 1 1
0
Sample Output 1
AC
2
DDHH
2
No moves needed
2
2
DDHH
2
No moves needed
2
Hints
第一組範例即為上頁最左邊之圖。
對於 50%測試資料，每個檔案僅有1筆資料。
對於100%測試資料，每個檔案包含的盤面數 <= 30。
Problem Source
原TIOJ1673 / 建國中學99年校內培訓contest #2 prob 5
problem setter:worm
source:PKU Online Judge 2286
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |