1385: #6033. 「雅礼集训 2017 Day2」棋盘游戏
[Creator : ]
Description
Alice 和 Bob 在玩一个游戏，给出一张 $n \times m$ 的棋盘，上面有一些点是障碍，游戏的开始，Alice 选定棋盘上任意一个不是障碍的格子，并且将一枚棋子放在其中，然后 Bob 先手，两人轮流操作棋子，每次操作必须将棋子从当前位置移动到一个相邻的无障碍且未经过的格子（即每个格子不允许经过两次），不能操作的人输，如果两人都按照最优策略操作，请问初始时 Alice 将棋子放在哪些格子上有必胜策略？
Input
第一行，两个正整数 $n,m$。
接下来输入一个 $n \times m$ 的字符矩阵，$n$ 行 $m$ 列，. 表示空的格子，# 表示有障碍的格子。
接下来输入一个 $n \times m$ 的字符矩阵，$n$ 行 $m$ 列，. 表示空的格子，# 表示有障碍的格子。
Output
第一行，一个正整数 $\text{ans}$，为 Alice 有必胜策略的格子的个数。
接下来 $\text{ans}$ 行，每行一个坐标 $(x, y)$ 表示第 $x$ 行第 $y$ 列是一个 Alice 有必胜策略的初始位置，以矩阵的左上角 $(1, 1)$，右下角为 $(n, m)$。
接下来 $\text{ans}$ 行，每行一个坐标 $(x, y)$ 表示第 $x$ 行第 $y$ 列是一个 Alice 有必胜策略的初始位置，以矩阵的左上角 $(1, 1)$，右下角为 $(n, m)$。
Constraints
对于 $20\%$ 的数据，$n, m \leq 4$；
对于 $60\%$ 的数据，$n, m \leq 10$；
对于 $100\%$ 的数据，$1 \leq n, m \leq 100$。
对于 $60\%$ 的数据，$n, m \leq 10$；
对于 $100\%$ 的数据，$1 \leq n, m \leq 100$。
Sample 1 Input
2 2
#.
..
Sample 1 Output
2
1 2
2 1
如果 Alice 将棋子放在 $(1, 2)$，Bob 只能将其移动到 $(2, 2)$，Alice 再移动到 $(2, 1)$，此时 Bob 无法移动，Alice 获胜；
如果 Alice 将棋子放在 $(2, 1)$，类似以上情况；
如果 Alice 将棋子放在 $(2, 2)$，Bob 可以将棋子任意移动到 $(1, 2)$ 或 $(2, 1)$，此时 Bob 获胜。
如果 Alice 将棋子放在 $(2, 1)$，类似以上情况；
如果 Alice 将棋子放在 $(2, 2)$，Bob 可以将棋子任意移动到 $(1, 2)$ 或 $(2, 1)$，此时 Bob 获胜。