TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

6.2% (1/16)

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 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

Sample Output

AC
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10