問題文
H 行 W 成排的方块和棋子 1 有一个。i (1 ≦ i ≦ H) 行目 j (1 ≦ j ≦ W) 选择列中的单元格。 我们称之为 (i,j) 。此时左上方的方块就是 (1,1) 使右下角的正方形成为正方形。 (H,W) 。还有,质量 除 (1,1) 之外的一些方格上有障碍物。一对热爱游戏的兄妹正在尝试用这些方块和棋子来玩下面的游戏。
- 首先,这些碎片被聚集在一起。 将其放入 (1,1) 。
- 玩家轮流移动棋子。 1 津田? 1 右下角? 1 它必须移动到右侧无障碍物之一。换句话说,棋子是正方形的。 (i,j) ,质量 (i+1,j) 镰须 (i+1,j+1) 镰须 (i,j+1) 必须将其移至任何没有障碍物的方格。不过,此时还不能将其移出网格。也就是说,i = H 无法向下移动或移至右下角,j = W 无法移至右下或右侧。
- 玩家轮流进行,轮流中无法移动棋子的玩家失败(另一方获胜)。
2 当所有人都采取最优策略获胜时,先发者还是后发者,哪一个获胜?
入力
输入是按以下格式从标准输入给出的。
H W
S_{1,1}S_{1,2}..S_{1,W}
S_{2,1}S_{2,2}..S_{2,W}
:
S_{H,1}S_{H,2}..S_{H,W}
- 1 行中,2 整数 H (1 ≦ H ≦ 100), W (1 ≦ W ≦ 100) 用空格分隔。这意味着网格中的行数是 H,网格中的列数为 来自行 W 。 一个整数
- 2 从线 H 行提供有关正方形的信息。其中
给出了 i (1 ≦ i ≦ H) 行中,W 字符。其中 j (1 ≦ j ≦ W) 字符 S_{i,j} 是质量
代表有关 (i,j) 的信息
字符是
#或.。 如果#则质量 (i,j) 表示有障碍物,.则质量 (i,j) 表示没有障碍物。然而,S_{1,1} 是 仅由.有保证。
部分点
针对此问题设置了部分分数。
- H ≦ 4 和 满足 W ≦ 4 的数据集 如果您正确回答 1 ,30 点。 如果您对除上述数据集之外的所有满足
- 如果所有测试用例都回答正确,除了上述之外 70 点。 如果您对除上述数据集之外的所有满足
出力
如果第一个玩家获胜 First ,如果第二个移动者获胜
在 Second 它被转换为格式 1 行输出。在输出末尾插入换行符。
入力例1
2 3 .#. ...
出力例1
First
游戏例如如下进行。o 代表棋子的位置。
o#. ...
- 1 转:棋子是正方形 它位于 (1,1) 。您可以将棋子向下移动或移动到右下角。先动者将棋子向下移动。 它位于
.#. o..
- 2 转:棋子是正方形 它位于 (2,1) 。棋子只能向右移动。第二步,棋子移到右边。 它位于
.#. .o.
- 3 转:棋子是正方形 它位于 (2,2) 。棋子只能向右移动。先动者将棋子移至右侧。 它位于
.#. ..o
- 4 转:棋子是正方形 它位于 (2,3) 。如果你平局,你就输了,因为你无法移动你的棋子。
无论第二手棋子如何走,先手棋只要走得恰当,就能获胜。 First 。
入力例2
4 4 .... ...# .... .#..
出力例2
Second
无论先手如何走棋,后手只要采取适当的走法就可以获胜。 Second 。
入力例3
11 44 ............................................ ............................................ ............................................ .....#.....#####....####.....####....####... ....#.#....#....#..#....#...#....#..#....#.. ....#.#....#....#..#.............#..#....#.. ...#####...#####...#..........###....####... ...#...#...#....#..#.............#..#....#.. ..#.....#..#....#..#....#...#....#..#....#.. ..#.....#..#....#...####.....####....####... ............................................
出力例3
Second