AT_arc038_b.[ARC038B] マス目と駒

有一个 $H$ 行 $W$ 列的格子和一个棋子。我们将第 $i$ 行第 $j$ 列的格子称为格子 $(i,j)$，其中 $1 \leq i \leq H$，$1 \leq j \leq W$。此时，左上角的格子为 $(1,1)$，右下角的格子为 $(H,W)$。此外，除了格子 $(1,1)$ 以外，有一些格子上放置了障碍物。一对喜欢玩游戏的兄妹打算用这个格子和棋子进行如下的游戏。

• 最开始，将棋子放在格子 $(1,1)$ 上。
• 每位玩家在自己的回合，必须将棋子移动到下方、右下方或右方的某一个没有障碍物的格子。也就是说，当棋子在格子 $(i,j)$ 时，可以将棋子移动到 $(i+1,j)$、$(i+1,j+1)$ 或 $(i,j+1)$ 中没有障碍物的任意一个格子。但此时，不能将棋子移出格子范围。即当 $i=H$ 时，不能向下或右下移动；当 $j=W$ 时，不能向右下或右移动。
• 双方轮流操作，无法移动棋子的玩家判负（另一方获胜）。

假设两人都采取最优策略，问先手还是后手会获胜？

输入通过标准输入给出，格式如下：

$H$ $W$
$S_{1,1} S_{1,2} \ldots S_{1,W}$
$S_{2,1} S_{2,2} \ldots S_{2,W}$
$\vdots$
$S_{H,1} S_{H,2} \ldots S_{H,W}$

• 第 $1$ 行包含两个整数 $H\ (1 \leq H \leq 100)$、$W\ (1 \leq W \leq 100)$，分别表示格子的行数和列数。
• 接下来的 $H$ 行，每行包含 $W$ 个字符，表示格子的状态。第 $i$ 行第 $j$ 个字符 $S_{i,j}$ 表示格子 $(i,j)$ 的信息，字符为 # 或 .。# 表示该格子有障碍物，. 表示该格子无障碍物。保证 $S_{1,1}$ 一定为 .。

如果先手获胜，输出 First；如果后手获胜，输出 Second。输出需换行。

部分分

本题设有部分分。

• 若能通过 $H \leq 4$ 且 $W \leq 4$ 的数据集 $1$，可获得 $30$ 分。
• 若能通过所有测试点，可获得额外 $70$ 分。

样例解释 1

游戏的进行过程例如如下。o 表示棋子的位置。

o#.
...

• 第 1 回合：棋子在 $(1,1)$，可以向下或右下移动。先手将棋子向下移动。

.#.
o..

• 第 2 回合：棋子在 $(2,1)$，只能向右移动。后手将棋子向右移动。

.#.
.o.

• 第 3 回合：棋子在 $(2,2)$，只能向右移动。先手将棋子向右移动。

.#.
..o

• 第 4 回合：棋子在 $(2,3)$，后手无法移动棋子，因此后手失败。

无论后手如何移动棋子，先手都可以通过合适的移动方式获胜，因此输出 First。

样例解释 2

无论先手如何移动棋子，后手都可以通过合适的移动方式获胜，因此输出 Second。

由 ChatGPT 4.1 翻译