TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

22.2% (4/18)

Tags

Description

井字棋,又稱圈圈叉叉,是個十分有名的遊戲。然而,一般的井字棋只要雙方有使用最佳策略,最後一定會平手。因此,這裡介紹一個新的變種。由於是井字棋的加強版,我們稱它為「井井井井字棋」。

井井井井字棋的進行與井字棋有些相似,但是有兩個不同點:
(1) 在5*5的盤面上進行。(沒錯,「井井井井」的名稱就是這麼來的)
(2) 每輪可以畫兩個(圈圈或叉叉)。

井井井井字棋第一輪一定是圈圈先走。因為每輪畫兩個,所以進行11輪之後,一共有22個格子被劃過了(留下三個空格),這時遊戲結束。而判斷勝負的方法如下:
(1) 首先,將最後三個空格填成叉叉。
(2) 對於五個橫列、五格直列和兩條對角線,如果該線上五個符號有至少四個相同,則代表該符號的玩家獲得一分。分數較高者獲勝。如果兩邊分數相同,則平手。

以下是一個遊戲進行的過程範例:(由左到右、由上到下)

最後結果是圈圈4分、叉叉3分,故圈圈獲勝。

這裡有個簡單的互動式程式,可以自行編譯之後玩玩看這個遊戲。

了解井井井井字棋之後,喵喵很好奇這個遊戲到底會不會和井字棋一樣,如果雙方都用最佳策略,最後一定會平手。為了協助他研究這個遊戲,你的任務是幫忙撰寫一個程式,判斷一個進行到一半的盤面,如果雙方都使用最佳策略的話,最後的結果會是誰贏,或者是平手。

以下舉幾個「最佳策略」的例子:

(1)

這個例子中,下一輪是輪到圈圈。當前圈圈和叉叉各有三分,但是圈圈不可能再獲得任何分數,也就是他已經沒有勝算了。但是他卻可以下在以灰色標示的兩個格子,使遊戲平手。對於圈圈其他所有的策略,都會使得叉叉獲勝,因此這是圈圈的最佳策略,答案是平手。

(2)

這個例子中,下一輪是輪到圈圈。圈圈唯一拿到三分的方法是下在兩個黑色的位置,然而這樣會導致叉叉可以再多拿到一分(黃色格子)。所以這時圈圈必輸無疑,答案是叉叉獲勝。在這種情況也可以說,所有的下法都是最佳策略。

(3)

這個例子中,下一輪是輪到叉叉。叉叉只要下在兩個灰色格子,就會變成(2)的局面,因此這是叉叉的最佳策略,答案是叉叉獲勝。
從這個例子也可以發現,最佳策略不一定只有一種;在此例中,下在兩個星號的位置也會導致叉叉贏,因此這也是另一種最佳策略。

Input Format

輸入的第一行有一個整數T,代表有T個盤面要判斷。
接下來每五行代表一個盤面,每行都是一個長度為5的字串,只由OX.構成。

保證盤面一定是合法的。以下以$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

Output Format

對於每個盤面,如果最後會是圈圈贏,請輸出一行O win;如果最後會是叉叉贏,請輸出一行X win;如果最後會平手,請輸出一行Draw(皆不含引號)。

Sample Input 1

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

Sample Output 1

O win
Draw
X win
X win

Hints

這個遊戲如果從頭開始的話,在雙方都最佳策略時是平手。(爆搜花了60G的記憶體和五個小時(?))

Problem Source

Problem set by Yihda Yol
題目取自2018年臺大資工系資料結構與演算法作業三

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 262144 262144 1 2 3 4 5 6 7
1 2500 262144 262144 2 3 4 5 6 7
2 2500 262144 262144 3 4 5 6 7
3 2500 262144 262144 4 5 6 7
4 7500 262144 262144 5 6 7
5 6500 1048576 262144 6 7
6 4500 1048576 262144 7