#P18532. Clever Cell Choices

Clever Cell Choices

Clever Cell Choices

两名玩家在一个 N×MN\times M 的网格上进行游戏:

  • 最初,每个格子为空或已被占据。
  • 两人轮流向一个空格放置一枚石子,从而占据这个格子。除第一枚石子可以放在任意空格外,之后每枚新石子都必须与上一枚刚放置的石子相邻。两个格子共用一条边时才相邻。
  • 当轮到的玩家无法按规则放置石子时,游戏结束,该玩家失败,另一名玩家获胜。

如果先手把第一枚石子放到某个空格后,在双方都采取最优策略的情况下能够获胜,则称这个空格为一个获胜起始格。

给出网格的初始状态,求获胜起始格的数量。

输入格式

第一行包含两个整数 N,MN,M(1≤N,M≤501\le N,M\le50),表示网格的行数和列数。

接下来 NN 行,每行一个长度为 MM 的字符串。第 ii 行第 jj 个字符描述格子 (i,j)(i,j) 的初始状态:. 表示空格,# 表示已占据。

输出格式

输出一行一个整数,表示获胜起始格的数量。

原样例 1

3 3
#.#
...
#.#
4

原样例 2

3 3
..#
...
...
0

原样例 3

1 4
...#
2