1644 . 棋盤策略遊戲
TopCoder
Tags
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
.xx
...
x.x
Sample Output 1
WIN
2 3
3 2
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 |