井字棋,又稱圈圈叉叉,是個十分有名的遊戲。然而,一般的井字棋只要雙方有使用最佳策略,最後一定會平手。因此,這裡介紹一個新的變種。由於是井字棋的加強版,我們稱它為「井井井井字棋」。
井井井井字棋的進行與井字棋有些相似,但是有兩個不同點:
(1) 在5*5的盤面上進行。(沒錯,「井井井井」的名稱就是這麼來的)
(2) 每輪可以畫兩個(圈圈或叉叉)。
井井井井字棋第一輪一定是圈圈先走。因為每輪畫兩個,所以進行11輪之後,一共有22個格子被劃過了(留下三個空格),這時遊戲結束。而判斷勝負的方法如下:
(1) 首先,將最後三個空格填成叉叉。
(2) 對於五個橫列、五格直列和兩條對角線,如果該線上五個符號有至少四個相同,則代表該符號的玩家獲得一分。分數較高者獲勝。如果兩邊分數相同,則平手。
以下是一個遊戲進行的過程範例:(由左到右、由上到下)
最後結果是圈圈4分、叉叉3分,故圈圈獲勝。
這裡有個簡單的互動式程式,可以自行編譯之後玩玩看這個遊戲。
了解井井井井字棋之後,喵喵很好奇這個遊戲到底會不會和井字棋一樣,如果雙方都用最佳策略,最後一定會平手。為了協助他研究這個遊戲,你的任務是幫忙撰寫一個程式,判斷一個進行到一半的盤面,如果雙方都使用最佳策略的話,最後的結果會是誰贏,或者是平手。
以下舉幾個「最佳策略」的例子:
(1)
這個例子中,下一輪是輪到圈圈。當前圈圈和叉叉各有三分,但是圈圈不可能再獲得任何分數,也就是他已經沒有勝算了。但是他卻可以下在以灰色標示的兩個格子,使遊戲平手。對於圈圈其他所有的策略,都會使得叉叉獲勝,因此這是圈圈的最佳策略,答案是平手。
(2)
這個例子中,下一輪是輪到圈圈。圈圈唯一拿到三分的方法是下在兩個黑色的位置,然而這樣會導致叉叉可以再多拿到一分(黃色格子)。所以這時圈圈必輸無疑,答案是叉叉獲勝。在這種情況也可以說,所有的下法都是最佳策略。
(3)
這個例子中,下一輪是輪到叉叉。叉叉只要下在兩個灰色格子,就會變成(2)的局面,因此這是叉叉的最佳策略,答案是叉叉獲勝。
從這個例子也可以發現,最佳策略不一定只有一種;在此例中,下在兩個星號的位置也會導致叉叉贏,因此這也是另一種最佳策略。
輸入的第一行有一個整數T,代表有T個盤面要判斷。
接下來每五行代表一個盤面,每行都是一個長度為5的字串,只由O
、X
、.
構成。
保證盤面一定是合法的。以下以$X$代表初始盤面已經進行的輪數。
子任務(測資) | 額外限制 | 分數 |
1 (0) | $X=11$ | 5 |
2 (0~1) | $X\geq 10$ | 15 |
3 (0~2) | $X\geq 8$ | 15 |
4 (0~3) | $X\geq 7$ | 15 |
5 (0~4) | $X\geq 6$ | 30 |
6 (0~5) | $X\geq 5$ | 10 |
7 (0~6) | $X\geq 4$ | 5 |
對於每個盤面,如果最後會是圈圈贏,請輸出一行O win
;如果最後會是叉叉贏,請輸出一行X win
;如果最後會平手,請輸出一行Draw
(皆不含引號)。
這個遊戲如果從頭開始的話,在雙方都最佳策略時是平手。(爆搜花了60G的記憶體和五個小時(?))
Problem set by Yihda Yol
題目取自2018年臺大資工系資料結構與演算法作業三
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 5 |
2 | 0~1 | 15 |
3 | 0~2 | 15 |
4 | 0~3 | 15 |
5 | 0~4 | 35 |
6 | 0~5 | 10 |
7 | 0~6 | 5 |