← 返回题目列表

Codeforces · 142/D

D. 帮助怪物史莱克和驴 2

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

在学会了(在 Codeforces 参与者的帮助下)如何最佳地玩上一轮的纸牌游戏后,史莱克和驴子(你可能还记得,他们现在也生活在遥远的王国)决定退出无聊的纸牌游戏并与玩具士兵一起玩。

游戏规则如下:有一个战场,其大小为n×m个方格,某些方格内有玩具士兵(绿色的是史莱克,红色的是驴子)。此外,该区域的n行每行最多包含两名士兵。在移动过程中,玩家应选择属于他的不少于 1 且不多于 k 的士兵,并让他们攻击或撤退。

攻击是指将所有选定的士兵沿着他们所站的路线移动到敌方士兵的方向(如果敌方士兵在这条线上)。如果该线上没有敌方士兵,则该线上选定的士兵可以在玩家移动过程中向任意方向移动。每个选定的士兵必须至少移动一个单元格。不同的士兵可以移动不同数量的单元格。在攻击期间,士兵不得穿过其他士兵站立的牢房(或攻击前站立的牢房)。也不允许超出战场或在其他士兵站立的牢房(或攻击前站立的地方)完成攻击。

撤退是指将所有选定的士兵沿着他们所站立的战线移动到敌方士兵的方向(如果敌方士兵在这条战线上)。其他规则重复攻击规则。

例如,假设原始战场具有以下形式(此处符号“G”标记史莱克的绿色士兵,符号“R”标记驴子的红色士兵):

-G-R--R-G-

假设 k = 2 并且史莱克先移动。如果他决定攻击,那么在他移动之后,战场会是这样的:

--GR- --GR- -G-R--RG-- -R-G- -RG--

如果在前面的例子中史莱克决定撤退,那么在他移动之后,战场会是这样的:

G--R- G--R- -G-R--R--G -R-G- -R--G

另一方面,以下字段不能由史莱克的正确动作产生:

G--R- ---RG --GR--RG-- -R-G- GR---

史莱克开始游戏。出招就是按规则进攻或撤退。无法采取行动的玩家失败,他的对手获胜。如果史莱克和驴子继续处于上一轮问题的黄色药丸之下,则确定给定玩具士兵游戏的获胜者。因此,他们总是以最佳方式进行比赛(也就是说,如果可能的话,他们会尝试获胜,或者如果他们无法获胜,则通过确保比赛永远持续下去以平局结束比赛)。

输入

第一行包含空格分隔的整数 n、m 和 k (1 ≤ n, m, k ≤ 100)。那么n行每行包含m个字符。这些字符属于集合{“-”,“G”,“R”},分别表示战场的空闲单元,史莱克士兵占据的单元和驴子士兵占据的单元。

保证每行士兵不超过两名。

输出

如果史莱克在给定的玩具士兵游戏中获胜,则打印“First”(不带引号)。如果 Donkey 获胜,则打印“Second”(不带引号)。如果游戏永远继续下去,则打印“Draw”(也不带引号)。

示例

输入 #1

2 3 1
R-G
RG-

输出 #1

First

输入 #2

3 3 2
G-R
R-G
G-R

输出 #2

Second

输入 #3

2 3 1
-R-
-G-

输出 #3

Draw

输入#4

2 5 2
-G-R-
-R-G-

输出#4

First