Description |
井字棋,又稱圈圈叉叉,是個十分有名的遊戲。然而,一般的井字棋只要雙方有使用最佳策略,最後一定會平手。因此,這裡介紹一個新的變種。由於是井字棋的加強版,我們稱它為「井井井井字棋」。
井井井井字棋的進行與井字棋有些相似,但是有兩個不同點:
井井井井字棋第一輪一定是圈圈先走。因為每輪畫兩個,所以進行11輪之後,一共有22個格子被劃過了(留下三個空格),這時遊戲結束。而判斷勝負的方法如下: 以下是一個遊戲進行的過程範例:(由左到右、由上到下) 這裡有個簡單的互動式程式,可以自行編譯之後玩玩看這個遊戲。 了解井井井井字棋之後,John Ceena很好奇這個遊戲到底會不會和井字棋一樣,如果雙方都用最佳策略,最後一定會平手。為了協助他研究這個遊戲,你的任務是幫忙撰寫一個程式,判斷一個進行到一半的盤面,如果雙方都使用最佳策略的話,最後的結果會是誰贏,或者是平手。 以下舉幾個「最佳策略」的例子:
(1)
(2)
(3) |
Input / Output Format |
請由stdin讀入、stdout輸出。
輸入的第一行有一個整數T,代表有T個盤面要判斷。 |
Sample Input | Sample Output |
4 OXX.. XOOX. OXOOO OXOOX OXOXX XX.O. XX.OO XXXOO XX.XO .OOOO XOOOO XXXXO X.XOO XO... OOX.X XOOOO XXXXO X.XOO XO... OO... |
O win Draw X win X win |
Subtasks |
Subtask 1 (5 pt): 輸入已經進行了11輪。(也就是說,只要判斷到底是誰贏就好。) Subtask 2 (15 pt): 輸入至少已經進行了10輪。 Subtask 3 (15 pt): 輸入至少已經進行了8輪。 Subtask 4 (15 pt): 輸入至少已經進行了7輪。 Subtask 5 (35 pt): 輸入至少已經進行了6輪。 Subtask 6 (10 pt): 輸入至少已經進行了5輪。 Subtask 7 (5 pt): 輸入至少已經進行了4輪。 |
Suggestions & Hints |
(1) 搜尋所有下一步有可能出現的盤面,並記錄它們的結果。假設當前是圈圈的回合,所有下一步的盤面中若有任何一個是圈圈必勝,那這個盤面也是圈圈必勝;如果都沒有圈圈必勝的話,找有沒有平手的盤面,若有,則是平手;如果還是沒有,那就是叉叉必勝了。以虛擬碼舉例: WhoWin(board, round) { if (board is ended) return Evaluate(board); if (round == 'X') { result = "O win"; for (nextboard in all possible next move) { nextresult = WhoWin(nextboard, 'O'); if (nextresult == "X win") { result = "X win"; } else if (nextresult == "Draw" && result == "O win") { result = "Draw"; } } return result; } else { // ... likewise } } (2) 搜尋過程中,有可能下的順序不同但導致了同一個盤面。可以用一個unordered_map把所有已經算過的盤面記錄下來,這樣下次遇到這個盤面就不需要再算一次了。 (3) 這個盤面總共有25格,每一格有三種狀態(圈圈、叉叉或空白),因此每一格可以用兩個bit表示,也就是一個long long就足以表示整個盤面了。可以用這個方法把盤面的結果存在unordered_map。 (4) 假設當前是圈圈的回合,如果搜到任何一個下一步的盤面是圈圈必勝,就可以直接確定這個盤面是圈圈必勝,而不必繼續搜尋下去了。再進一步想想看,有沒有可能在某些情況下,某個盤面到底是圈圈必勝還是平手其實完全不影響結果呢?(可以看成簡化版的alpha-beta pruning。) |