UVa OJ 127 - "Accordian" Patience (“手風琴”紙牌)

Time limit: 3.000 seconds

限時：3.000秒

You are to simulate the playing of games of "Accordian" patience, the rules for which are as follows:

模拟玩一個“手風琴”紙牌遊戲，規則如下：

Deal cards one by one in a row from left to right, not overlapping. Whenever the card matches its immediate neighbour on the left, or matches the third card to the left, it may be moved onto that card. Cards match

if they are of the same suit or same rank. After making a move, look to see if it has made additional moves possible. Only the top card of each pile may be moved at any given time. Gaps between piles should be closed up as soon as they appear by moving all

piles on the right of the gap one position to the left. Deal out the whole pack, combining cards towards the left whenever possible. The game is won if the pack is reduced to a single pile.

按從左至右的順序發牌，并擺成一行，發牌不要互相重疊。遊戲中一旦出現任何一張牌與它左邊的第一張或第三張“比對”，即花色或點數相同，則須立即将其移動到那張牌上面。如果牌被移動後又出現了上述情況，則需再次向左移動。每疊牌隻能移動最上面的一張。如果一疊牌被移空，應該立即将右邊各疊整體向左移動，補上這個空隙。依次将整副牌都發完，并不斷的向左合并。如果全部移動結束後整副牌都放成了一疊，則遊戲勝利。

Situations can arise where more than one play is possible. Where two cards may be moved, you should adopt the strategy of always moving the leftmost card possible. Where a card may be moved either one position to

the left or three positions to the left, move it three positions.

玩上幾次你就會遇到一些狀況。如果同時有兩張牌都可以移動，你應該采取的政策是移動最左邊的牌（當然必須是可以移動的）。當一張牌既可以移動到左邊第一張，又可以移動到左邊第三張時，應移動到左邊第三張上面。

Input data to the program specifies the order in which cards are dealt from the pack. The input contains pairs of lines, each line containing 26 cards separated by single space characters. The final line of the input

file contains a # as its first character. Cards are represented as a two character code. The first character is the face-value (A=Ace, 2-9, T=10, J=Jack, Q=Queen, K=King) and the second character is the suit (C=Clubs, D=Diamonds, H=Hearts, S=Spades).

輸入到程式中的資料指定了一副牌的順序。每組輸入包括兩行，每行26張牌，牌與牌之間用空格隔開。以#号開頭的一行作為輸入的結束行。每張牌由兩個字元表示，第一個字元是點數：（A、 2-9、T=10、J、Q, K）；第二個字元是花色：（C=梅花、D=方塊、H=紅心、S=黑桃）。

One line of output must be produced for each pair of lines (that between them describe a pack of 52 cards) in the input. Each line of output shows the number of cards in each of the piles remaining after playing

"Accordian patience" with the pack of cards as described by the corresponding pairs of input lines.

每兩行輸入（定義了一副52張牌的順序）必須産生一行輸出。每行輸出包括剩下的疊數以及每疊中的牌數。

QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C 6S

8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C 5C

AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD KD

AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS KS

#

6 piles remaining: 40 8 1 1 1 1

1 pile remaining: 52

(譯注：第一個數字為剩下的疊數，當疊數為1時，後面輸出“pile remaining: ”，否則輸出“piles remaining: ”。接下來從左至右輸出各疊牌的數量）

這兩天UVa OJ的伺服器老是不穩定，送出的解答一直“In judge queue”，不得不停工了很長時間！下面的代碼用幾百組随機資料測試過，與提供的所謂正确答案比對，結果是完全相同的。不管怎樣思路應該不會錯，是以先貼上來，也好清空代碼做下一題。如果OJ出來沒有AC，再修改也不遲。（更新：OJ出來了，AC，0.772秒）

解這道題前務必認真的了解題意，一點小誤差都會引起算法的區大差别。最好先拿副撲克牌先玩幾遍，熟練的過程中思路自然就産生了，還可能會發現一些技巧。

總體還是采用步進疊代的方法來解，每發一張牌就執行所有可能的移動，然後再發下一張。直到所有的牌都發完，統計并輸出結果。存儲牌疊應采用二維動态數組，我使用的是兩層vector，如果追求效率可将外層的vector改為list，但實作的代碼會比較複雜。

按照題目要求，每次移動一張牌時，應一次性向左移動到再也不能移動的位置上。此時這張牌的右邊就可能再次出現可以移動的牌。是以，發牌後可以執行的操作是：将一張牌（新發的牌應放在最後作為第一次移動的牌）向左移動完畢後，向右查找第一個可以移動的牌；找到後再向左移動，然後再從移動後的位置向右查找，以此類推，直到再也找不到可以移動的牌為止。

用三重循環來解決問題，最外層的循環就是按順序發牌。每次發一張牌就将這張牌放到最後作為新的一疊。中間一層循環用來向右遍例每一張可以移動的牌，找到後就向左移動。最内的循環就是查找目前牌可以移動到的位置（最左邊的）。

從該題的Statics來看，OJ給出的測試資料量貌似比較大，是以要比較小心的實作。為了加快運算，我沒有使用特别的資料結構來轉存牌面，這也是沒有必要的，完全可以用原輸入的字元進行處理。CARD結構體隻是用于表示兩個字元的指針。

這道題本身不難，圖釋就劃不來了，還是看代碼吧。