CF142D Help Shrek and Donkey 2
题目描述
学会了（在 Codeforces 选手们的帮助下）如何最佳地玩上一场的纸牌游戏之后，Shrek 和 Donkey（你应该还记得，他们现在也住在 Far Far Away 王国）决定不再玩无聊的纸牌游戏，转而用玩具士兵来玩游戏。
游戏规则如下：有一个战场，其大小为 $n \times m$ 格子，有些格子里有玩具士兵（绿色的属于 Shrek，红色的属于 Donkey）。此外，战场的每一行最多只包含两个士兵。每一回合，玩家需要选择至少 $1$ 个、至多 $k$ 个属于自己的士兵，并让它们“进攻”或者“撤退”。
“进攻”是指，将所有选定的士兵沿着它们所在的那一行，朝向敌军士兵的方向前进（如果本行上有敌人）。如果本行上没有敌军士兵，那么该行上的选定士兵可以在玩家本回合中朝任意方向移动。每个被选中的士兵至少要移动一格。不同的士兵可以移动不等距离。进攻时，士兵不能穿越其他士兵所在（或在本次进攻操作前所在）的格子。士兵也不能走出战场边界，也不能在进攻结束时停在其他士兵原先或当前所在的格子上。
“撤退”是指，将所有选定的士兵沿着它们所在的那一行，背离敌军士兵的方向后退（如果本行上有敌人）。其他规则与进攻相同。
例如，假定初始战场如下（"G" 表示 Shrek 的绿色士兵，"R" 表示 Donkey 的红色士兵）：
`-G-R-
-R-G-
` 假定 $k=2$，Shrek 先手。如果他选择进攻，那么他的回合结束后，战场可能为： `--GR- --GR- -G-R-
-RG-- -R-G- -RG--
` 如果在上面的例子中，Shrek 选择撤退，则回合结束后，战场可能为： `G--R- G--R- -G-R-
-R--G -R-G- -R--G
` 另一方面，以下这些场景不能通过 Shrek 的正确操作得到： `G--R- ---RG --GR-
-RG-- -R-G- GR---
` Shrek 首先行动。一轮操作就是按上述规则进攻或撤退。若某一方无法行动，则判该方输，对手获胜。如果双方都最佳操作（即能赢则争取必赢，若不能赢则努力令游戏无限进行下去），请判断本局游戏的获胜方。如果 Shrek 获胜，输出 "First"；如果 Donkey 获胜，输出 "Second"；如果游戏能无限进行下去，则输出 "Draw"。
-R-G-
` 假定 $k=2$，Shrek 先手。如果他选择进攻，那么他的回合结束后，战场可能为： `--GR- --GR- -G-R-
-RG-- -R-G- -RG--
` 如果在上面的例子中，Shrek 选择撤退，则回合结束后，战场可能为： `G--R- G--R- -G-R-
-R--G -R-G- -R--G
` 另一方面，以下这些场景不能通过 Shrek 的正确操作得到： `G--R- ---RG --GR-
-RG-- -R-G- GR---
` Shrek 首先行动。一轮操作就是按上述规则进攻或撤退。若某一方无法行动，则判该方输，对手获胜。如果双方都最佳操作（即能赢则争取必赢，若不能赢则努力令游戏无限进行下去），请判断本局游戏的获胜方。如果 Shrek 获胜，输出 "First"；如果 Donkey 获胜，输出 "Second"；如果游戏能无限进行下去，则输出 "Draw"。
输入格式
第一行包含空格分隔的整数 $n$、$m$ 和 $k$（$1 \leq n, m, k \leq 100$）。接下来 $n$ 行，每行包含 $m$ 个字符。这些字符只可能是 {"-", "G", "R"}，分别表示战场上的空位、Shrek 的士兵、Donkey 的士兵。
保证每行最多只有两个士兵。
输出格式
如果 Shrek 在该玩具士兵游戏中获胜，输出 "First"（不包含引号）；如果 Donkey 获胜，输出 "Second"；如果游戏可以无限进行，输出 "Draw"（也不包含引号）。
说明/提示
由 ChatGPT 5 翻译