QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#137. 筑墙游戏

Statistics

“Wall Making Game” 是一款风靡一时的双人棋盘游戏。

该游戏在一个 $H \times W$ 的棋盘上进行。棋盘上的每个格子要么是空地(empty),要么是标记点(marked),要么是墙(wall)。游戏开始时,棋盘上没有任何墙。

在这个游戏中,两名玩家轮流进行如下操作:

  1. 玩家选择一个空地(既不是标记点也不是墙)。如果玩家无法选择任何格子,则该玩家输掉比赛。
  2. 从所选格子出发,向四个方向(上、下、左、右)延伸,将沿途经过的格子(包括所选格子本身)全部变为墙,直到遇到现有的墙或棋盘边界为止。

注意,标记点在第 1 步中不能被选择,但在第 2 步中可以被变为墙。下图展示了一个玩家选择第 3 行第 4 列格子进行操作的示例。

图 1:Wall Making Game 的操作示例。

你的任务是编写一个程序,判断如果两名玩家在给定的初始棋盘上采取最优策略,哪位玩家会获胜。

输入格式

输入的第一行包含两个整数 $H$ 和 $W$ ($1 \le H, W \le 20$),分别表示棋盘的高度和宽度。接下来的 $H$ 行代表初始棋盘。每行包含 $W$ 个字符。

第 $i$ 行的第 $j$ 个字符如果是 ‘.’,表示第 $i$ 行第 $j$ 列的格子为空地;如果是 ‘X’,则表示该格子为标记点。

输出格式

如果先手玩家获胜,输出 “First”(不含引号);否则,输出 “Second”(不含引号)。

样例

样例输入 1

2 2
..
..

样例输出 1

Second

样例输入 2

2 2
X.
..

样例输出 2

First

样例输入 3

4 5
X....
...X.
.....
.....

样例输出 3

First

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.