TopCoder

Nekosyndrome
かわいいは正義!

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

23.7% (9/38)

Tags

SSC

Description


說到在棋盤上玩策略性遊戲,種類可說是多不勝數,這次將要提到的便是其中一種。

這種遊戲是這樣的:首先,既然是棋盤策略遊戲,理當有一個棋盤,這次我們使用的棋盤是由等大小的 $N×M$ 個正方形格子組成的(第 $i$ 列第 $j$ 行的座標為 $(i, j)$ ),

其中,有可能有某些格子上有障礙物占據著。之後,由玩家以公平的方式(如猜拳)決定先手與後手的順序。

由先手的玩家先開始,選擇棋盤上一個沒有被障礙物占領的空格,並在上面放置遊戲用的棋子並標記該格子。

之後從第二手開始,以後手、先手的順序不斷重複這個動作:每次將棋子移動到原本所在格子隔壁(上下左右四方向)的新格子(尚未被標記的格子),

並將該新格子標記。直到某一方在自己的回合無法移動格子時他(她)就輸了。


曉涵很喜歡跟她的朋友玩這個遊戲,因為她覺得這個遊戲很刺激,尤其是到後期的時候。但是很不幸的,她總是輸掉的那一方。

因此,她希望你能夠幫幫她,在已知是先手的情形之下,對於每一種棋盤判斷是不是有必勝的下法或者是其實根本贏不了(假設對手絕頂聰明,過程中絕對不會失誤)。

如果有必勝的下法的話,曉涵希望你只要提示她第一步就好,留剩下的部分讓她自己思考,因為曉涵明白,唯有靠自己認真思考,才是進步的不二法門!

Input Format

本題輸入的測試檔只有單筆測試資料,第一列有兩個整數 $N$、$M$。

之後有 $N$ 個橫列,每列有 $M$ 個連續的字元,這 $N×M$ 個字元將代表棋盤的狀況:字元 x(ascii值 120)代表該格為障礙物;字元 .(ascii值 46)代表該格為空格。

請參考範例輸入。


對於所有測試資料,保證 $1 ≤ N, M ≤ 100$,棋盤只會有字元 x 或 . 。

Output Format

如果有必勝方案,請輸出一行「WIN」(不含引號),之後對於所有必勝方案都輸出可行第一手的座標位置 $(R_i, C_i)$,一個方案一行。

順序以 $R_i$ 較小的優先輸出,若 $R_i$ 一樣則以 $C_i$ 較小的優先輸出。

而如果為必敗狀態,請只輸出一行「LOSE」(不含引號)。若當前盤面無法判斷勝負,請只輸出一行「TIE」(不含引號)。

Sample Input 1

3 3
.xx
...
x.x

Sample Output 1

WIN
2 3
3 2

Hints

Problem Source

原TIOJ1644 / Skyly & Shik Contest II (Problem E)

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 5
20 19 5

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 8000 131072 262144 1
1 8000 131072 262144 2
2 8000 131072 262144 3
3 8000 131072 262144 4
4 8000 131072 262144 5
5 8000 131072 262144 6
6 8000 131072 262144 7
7 8000 131072 262144 8
8 8000 131072 262144 9
9 8000 131072 262144 10
10 8000 131072 262144 11
11 8000 131072 262144 12
12 8000 131072 262144 13
13 8000 131072 262144 14
14 8000 131072 262144 15
15 8000 131072 262144 16
16 8000 131072 262144 17
17 8000 131072 262144 18
18 8000 131072 262144 19
19 8000 131072 262144 20