#P16298. [Ucpc2021]Board Game
[Ucpc2021]Board Game
题目描述
游戏由 个棋盘和 枚棋子组成。第 个棋盘是一个 的网格。
对每个棋盘,沿网格边从左上角顶点走到右下角顶点,每一步只能向右 R 或向下 D。选取两条长度为 的这样的路径作为围栏。除起点和终点外,两条路径不得相交;满足条件的围栏称为合法围栏布局。
下图中,(a) 合法,(b) 的两条路径在中间相交,(c) 中有路径并非只向右或向下,因此后两者均不合法。

游戏开始时,每个棋盘的左上角单元格各放置一枚棋子。先手 Jeyeon 与后手 Deokin 轮流操作:
- Jeyeon 的回合:选择任意一枚棋子,将其向右移动一格;
- Deokin 的回合:选择任意一枚棋子,将其向下移动一格。
棋子不能跨越围栏。无法进行合法移动的玩家输掉游戏。
给定所有棋盘的围栏布局,判断双方均采用最优策略时谁会获胜。
输入格式
第一行包含整数 。
随后依次给出 个棋盘。每个棋盘用三行描述:
- 第一行包含两个整数 ;
- 第二、三行各包含一个长度为 、仅由
R和D组成的字符串,表示两条围栏路径。
输入保证每一对路径构成合法围栏布局。
数据范围:
输出格式
若先手 Jeyeon 获胜,输出:
First
否则输出:
Second
样例 1
输入
2
3 2
RRDDD
DRDDR
1 2
DRR
RRD
输出
First
样例 1 的初始棋盘如下:

样例 2
输入
2
2 2
DRDR
RRDD
4 5
RDRDDRRRD
DDDRDRRRR
输出
Second