3848. [雅礼集训 2017 Day2] 棋盘游戏

【题目描述】

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

【输入格式】

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

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

【输出格式】

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

接下来 $ans$ 行，每行一个坐标 $(x, y)$ 表示第 $x$ 行第 $y$ 列是一个 $Alice$ 有必胜策略的初始位置，以矩阵的左上角 $(1, 1)$ ，右下角为 $(n, m)$ 。

【样例1输入】

2 2
#.
..

【样例1输出】

2
1 2
2 1

【样例1说明】

如果 $Alice$ 将棋子放在 $(1, 2)$ ，$Bob$ 只能将其移动到 $(2, 2)$ ，$Alice$ 再移动到 $(2, 1)$ ，此时 $Bob$ 无法移动，$Alice$ 获胜；

如果 $Alice$ 将棋子放在 $(2, 1)$ ，类似以上情况；

如果 $Alice$ 将棋子放在 $(2, 2)$ ，$Bob$ 可以将棋子任意移动到 $(1, 2)$ 或 $(2, 1)$ ，此时 $Bob$ 获胜。

【样例2】

点击下载样例2

【数据规模与约定】

对于 $20\%$ 的数据， $n, m \leq 4$ ；

对于 $60\%$ 的数据， $n, m \leq 10$ ；

对于 $100\%$ 的数据， $1 \leq n, m \leq 100$ 。

【来源】

LOJ