#bzoj1443. 游戏Game

游戏Game

题目原件:tmp.png

题目描述

AA\text{AA} 和小 YY\text{YY} 得到了《喜羊羊和灰太狼》的电影票,都很想去观看,但是电影票只有一张,于是他们用智力游戏决定胜负,赢得游戏的人可以获得电影票。

N×MN\times M 的迷宫中有一个棋子,小 AA\text{AA} 首先任意选择棋子放置的位置。然后,小 YY\text{YY} 和小 AA\text{AA} 轮流将棋子移动到相邻的格子里。游戏的规则规定,在一次游戏中,同一个格子不能进入两次,且不能将棋子移动到某些格子中去。当玩家无法继续移动棋子时,游戏结束,最后一个移动棋子的玩家赢得了游戏。

例如下图所示的迷宫,迷宫中"“表示棋子可以经过的格子,而#表示棋子不可以经过的格子:

.##
...
#.#

若小 AA\text{AA} 将棋子放置在(1,1)(1,1),则小 AA\text{AA} 则无论如何都无法赢得游戏。

而若小 AA\text{AA} 将棋子放置在(3,2)(3,2)(2,3)(2,3),则小 AA\text{AA} 能够赢得游戏。例如,小 AA\text{AA} 将棋子放置在(3,2)(3,2),小 YY\text{YY} 只能将它移动到(2,2)(2,2),此时小 AA 再将棋子移动到(2,3)(2,3),就赢得了游戏。

AA\text{AA} 和小 YY\text{YY} 都是绝顶聪明的小朋友,且从不失误。小 AA\text{AA} 到底能不能赢得这场游戏,从而得到珍贵的电影票呢?

输入格式

输入数据首先输入两个整数N,MN,M,表示了迷宫的边长。 接下来NN行,每行MM个字符,描述了迷宫。

输出格式

若小AA\text{AA}能够赢得游戏,则输出一行WIN,然后输出所有可以赢得游戏的起始位置,按行优先顺序输出 每行一个,否则输出一行LOSE(不包含引号)。

3 3
.##
...
#.#
WIN
2 3
3 2

数据范围与约定

对于30%30\%的数据,有1n,m51≤n,m≤5

对于100%100\%的数据,有1n,m1001≤n,m≤100