← 返回题目列表

AtCoder · arc038_b

B. 方块和棋子

中文机器翻译题面 查看原题

問題文

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