#P18532. Clever Cell Choices
Clever Cell Choices
Clever Cell Choices
两名玩家在一个 的网格上进行游戏:
- 最初,每个格子为空或已被占据。
- 两人轮流向一个空格放置一枚石子,从而占据这个格子。除第一枚石子可以放在任意空格外,之后每枚新石子都必须与上一枚刚放置的石子相邻。两个格子共用一条边时才相邻。
- 当轮到的玩家无法按规则放置石子时,游戏结束,该玩家失败,另一名玩家获胜。
如果先手把第一枚石子放到某个空格后,在双方都采取最优策略的情况下能够获胜,则称这个空格为一个获胜起始格。
给出网格的初始状态,求获胜起始格的数量。
输入格式
第一行包含两个整数 (),表示网格的行数和列数。
接下来 行,每行一个长度为 的字符串。第 行第 个字符描述格子 的初始状态:. 表示空格,# 表示已占据。
输出格式
输出一行一个整数,表示获胜起始格的数量。
原样例 1
3 3
#.#
...
#.#
4
原样例 2
3 3
..#
...
...
0
原样例 3
1 4
...#
2