bzoj#P1443. [JSOI2009]游戏Game

[JSOI2009]游戏Game

题目描述

给出一个 n×mn\times m 的网格,其中有一些障碍点。

现在两个人玩游戏,首先先手选定一个点,然后从后手开始轮流移动,不能移动者即输掉这次游戏。

规定不能移动到那些之前已经到过的格子上。

从一个点出发,称先手必胜当且仅当无论后手如何操作,先手总有一种策略取得胜利,此时称这个点为必胜起点。

输入格式

第一行两个整数 n,mn,m

接下来 nn 行,每行 mm 个字符描述这个迷宫。

若第 ii 行第 jj 列的字符是 # 说明点 (i,j)(i,j) 是障碍点,否则说明 (i,j)(i,j) 可以被经过。

输出格式

第一行一个字符串,若先手必胜,输出 WIN,否则输出 LOSE

若先手必胜,接下来每行输出一个必胜起点,按行优先顺序输出。

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

数据规模与约定

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

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