379 - Hi-Q

Hi -Q是一種棋盤遊戲，棋盤形狀類似十字形，共有33個棋格，於其上被放置32個棋子，正中央位置會是空的，遊戲的玩法是把一個棋子跨過另一個棋子到另一邊空的位置上(必須為垂直或水平地移動)，被跨過的棋子會被拿掉。遊戲的目地是儘可能地移除最多的棋子，本題只需要你模擬遊戲的進行。

棋盤的形狀如下，且每一個棋格皆被賦予1~33的編號：

                              1         2         3
                              4         5         6
          7         8         9        10        11        12        13
         14        15        16        17        18        19        20
         21        22        23        24        25        26        27
                             28        29        30
                             31        32        33

遊戲的一開始會在某些位置上放置棋子，而其他位置會是空的。遊戲的進行必須不斷的將一個棋子垂直或水平地跨過另一個棋子到另一邊空的位置上，且被跨過的棋子必須被移除，直到沒有辦法再移除多餘的棋子為止，此時你的程式必須回報在棋盤上還有棋子的編號之總和。移動棋子的原則為：儘可能的將棋子移動到編號最大的位置上去，若同時有不同的棋子可移動到相同的地方，請選擇位置編號最大的棋子。

例如下列中以X表示該位置上有棋子：

                              O         O         O
                              O         O         O
          O         O         O         X         O         X         O
          O         O         O         X         O         X         O
          O         O         O         O         X         O         O
                              O         O         O
                              O         O         O

其移動的順序為：將12移到26 -> 將25移到27 -> 將10移到24。最後有兩個棋子在24與27的位置上，24+27=51即為所求。

Input

輸入資料的第一列有一個整數N(1 <= N <= 10)表示測試資料的組數，接下來會有N組測試資料，每組資料會依序給定在哪些位置上被放置棋子，其值介於1 ~ 33，並以0表示該組測試資料結束。

Output

輸出資料共有N+2列，頭尾分別輸出"HI Q OUTPUT", "END OF OUTPUT"，並在這中間依序輸出每組資料的答案。

Sample Input

4
10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20
21 22 23 24 25 26   27 28 29 30 31 32 33 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0

Sample Output

HI Q OUTPUT
51                                                          
0
561  
98
END OF OUTPUT

原文出處