P15117 [ICPC 2024 LAC] Clever Cell Choices

两个玩家在一个 $N \times M$ 的网格上进行如下游戏： - 初始时，网格中的每个单元格要么是空的，要么被占据。 - 玩家轮流在一个空单元格上放置一颗棋子，占据该单元格。除了起始棋子可以放在任意空单元格外，每颗新放置的棋子必须与上一颗放置的棋子相邻。如果两颗棋子所在的单元格共享一条边，则它们相邻。 - 一旦有玩家无法根据上述规则放置棋子，游戏立即结束。此时，无法放置棋子的玩家输掉游戏，另一名玩家获胜。 一个**必胜起始单元格**是指：如果先手玩家将起始棋子放在该单元格上，并且双方都采取最优策略，那么先手玩家能够赢得游戏。给定初始网格的描述，你需要计算它有多少个必胜起始单元格。

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 50$），表示网格的尺寸。 接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串。第 $i$ 个字符串中的第 $j$ 个字符描述了单元格 $(i, j)$ 的初始状态。字符是 “.”（点号）表示空单元格，或是 “#”（井号）表示被占据的单元格。

输出一行一个整数，表示必胜起始单元格的数量。

翻译由 DeepSeek V3 完成