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 翻译