Problem1414--#6033. 「雅礼集训 2017 Day2」棋盘游戏

1414: #6033. 「雅礼集训 2017 Day2」棋盘游戏

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

Alice 和 Bob 在玩一个游戏,给出一张 n×m n \times m n×m 的棋盘,上面有一些点是障碍,游戏的开始,Alice 选定棋盘上任意一个不是障碍的格子,并且将一枚棋子放在其中,然后 Bob 先手,两人轮流操作棋子,每次操作必须将棋子从当前位置移动到一个相邻的无障碍且未经过的格子(即每个格子不允许经过两次),不能操作的人输,如果两人都按照最优策略操作,请问初始时 Alice 将棋子放在哪些格子上有必胜策略?

Input

第一行,两个正整数 n n nm m m
接下来输入一个 n×m n \times m n×m 的字符矩阵,n n nm m m 列,.表示空的格子,#表示有障碍的格子。

Output

第一行,一个正整数 ans \text{ans} ans,为 Alice 有必胜策略的格子的个数。
接下来 ans \text{ans} ans 行,每行一个坐标 (x,y) (x, y) (x,y) 表示第 x x x 行第 y y y 列是一个 Alice 有必胜策略的初始位置,以矩阵的左上角 (1,1) (1, 1) (1,1),右下角为 (n,m) (n, m) (n,m)

Sample Input Copy

2 2
#.
..

Sample Output Copy

2
1 2
2 1

HINT

对于 20% 20\% 20% 的数据,n,m≤4 n, m \leq 4 n,m4
对于 60% 60\% 60% 的数据,n,m≤10 n, m \leq 10 n,m10
对于 100% 100\% 100% 的数据,1≤n,m≤100 1 \leq n, m \leq 100 1n,m100

Source/Category