#P5531. [CCO 2019] Human Error
[CCO 2019] Human Error
题目描述
Justin 和 Donald 正在玩一种游戏:跳棋。你可能没有听说过,但是规则非常简单。
棋盘是一个矩形网格,在最开始时,每一格上恰好有一个棋子,并且每名玩家在棋盘上最少拥有一枚棋子。Justin 的棋子被标记为 J,而Donald的被标记为 D。
Justin 先下棋。在一次移动中,这位玩家可以移动自己的一枚棋子并吃掉相邻的一枚棋子**(不一定是对手的)**,随后轮到对手。如果当前玩家无法进行这样的操作,那么这位玩家就输了。
棋子 与 是相邻的,当且仅当 正好在 的上/下/左/右一格。
在理想的世界中,两人都是绝佳的逻辑学者,可以知晓每种棋盘上的最佳策略。然而这是不现实的。事实上,在游玩时,两人只会选择相对较好的走法。它到底有多好取决于 Justin 和 Donald 的误差常数,分别是 和 。
形式化地,拥有误差常数 的玩家会从所有可能的走法中选择其中 种组成方案集合。如果所有可能的走法数 ,那么方案集合仅包含这 种。之后,这位玩家会随机(等概率)地挑选其中的一种并依此进行操作。
两人在挑选方案组成集合时总会选择最优的方案,亦知晓对手也会选择最优方案。
请问 Justin 获胜的概率是多少?
输入格式
第一行两个正整数, 和 (用空格隔开)。
之后 行,每行 个字符,代表初始棋盘上的棋子分布(含义见题目描述)。
之后一行两个正整数, 和 (用空格隔开),含义见题目描述。
输出格式
一行,一个精确到 位小数的浮点数,代表 Justin 获胜的概率。
1 3
JJD
3 1
0.667
2 2
JJ
DD
3 1
0.000
提示
限制
初始棋盘棋子分布只用 J 和 D 这两种字符表示。
样例说明
样例1:
Justin 拥有 种移动的可能性,移动后分别为:(用 _ 表示空棋子)
_JD(第一颗向右移),J_J(第二颗向右移),J_D(第二颗向左移)。
对于情况 1,Justin 败。对于情况 2 和 3,Justin 胜。由于 Justin 的误差常数为 ,他会选择所有的情况,故胜率为,取 。
样例2:
Justin 拥有 种移动的可能性,移动后分别为:(用 _ 表示空棋子)
J_ _J J_ _J
DD DD DJ JD
然而,无论 Justin 选择哪种,他都没有可能赢。
之后 Donald 会选择最优的移动。他可以选择以下的方式击败对应的 Justin:
D_ _D J_ _J
_D D_ _D D_
故而 Justin 不可能赢。