当前没有测试数据。

棋盘游戏

题目描述

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

输入格式

第一行，两个正整数$n$，$m$。

接下来输入一个$n \times m$字符矩阵，$n$行$m$列，$.$表示空的格子，#表示有障碍的格子。

输出格式

第一行，一个正整数$ans$，为$Alice$有必胜策略的格子的个数。

接下来$ans$行，每行一个坐标$(x$，$y)$表示第$x$行第$y$列是一个$Alice$有必胜策略的初始位置（按照顺序输出，以$x$为第一关键字，$y$为第二关键字），以矩阵的左上角为$(1,1)$，右下角为$(n,m)$。

数据范围与提示

• 对于$20\%$的数据，$1 \leq n$，$m \leq 4$；
• 对于$60\%$的数据，$1 \leq n$，$m \leq 10$；
• 对于$100\%$的数据，$1 \leq n$，$m \leq 100$。

样例

2 2
#.
..

2
1 2
2 1