33OJ
登录 注册

#P5531. [CCO 2019] Human Error

[CCO 2019] Human Error

题目描述

Justin 和 Donald 正在玩一种游戏:跳棋。你可能没有听说过,但是规则非常简单。

棋盘是一个矩形网格,在最开始时,每一格上恰好有一个棋子,并且每名玩家在棋盘上最少拥有一枚棋子。Justin 的棋子被标记为 J,而Donald的被标记为 D。

Justin 先下棋。在一次移动中,这位玩家可以移动自己的一枚棋子并吃掉相邻的一枚棋子**(不一定是对手的)**,随后轮到对手。如果当前玩家无法进行这样的操作,那么这位玩家就输了。

棋子 AA 与 BB 是相邻的,当且仅当 AA 正好在 BB 的上/下/左/右一格。

在理想的世界中,两人都是绝佳的逻辑学者,可以知晓每种棋盘上的最佳策略。然而这是不现实的。事实上,在游玩时,两人只会选择相对较好的走法。它到底有多好取决于 Justin 和 Donald 的误差常数,分别是 JJ 和 DD。

形式化地,拥有误差常数 AA 的玩家会从所有可能的走法中选择其中 AA 种组成方案集合。如果所有可能的走法数 P≤A P \le A ,那么方案集合仅包含这 PP 种。之后,这位玩家会随机(等概率)地挑选其中的一种并依此进行操作。

两人在挑选方案组成集合时总会选择最优的方案,亦知晓对手也会选择最优方案。

请问 Justin 获胜的概率是多少?

输入格式

第一行两个正整数,RR 和 CC(用空格隔开)。

之后 RR 行,每行 CC 个字符,代表初始棋盘上的棋子分布(含义见题目描述)。

之后一行两个正整数,JJ 和 DD(用空格隔开),含义见题目描述。

输出格式

一行,一个精确到 33 位小数的浮点数,代表 Justin 获胜的概率。

1 3
JJD
3 1

0.667
2 2
JJ
DD
3 1

0.000

提示

限制

1≤R×C≤13 1 \le R \times C \le 13

1≤J,D≤13 1 \le J,D \le 13

初始棋盘棋子分布只用 J 和 D 这两种字符表示。

样例说明

样例1:

Justin 拥有 33 种移动的可能性,移动后分别为:(用 _ 表示空棋子)

_JD(第一颗向右移),J_J(第二颗向右移),J_D(第二颗向左移)。

对于情况 1,Justin 败。对于情况 2 和 3,Justin 胜。由于 Justin 的误差常数为 33,他会选择所有的情况,故胜率为23\frac{2}{3},取 0.6670.667。

样例2:

Justin 拥有 44 种移动的可能性,移动后分别为:(用 _ 表示空棋子)

J_ _J J_ _J
DD DD DJ JD

然而,无论 Justin 选择哪种,他都没有可能赢。

之后 Donald 会选择最优的移动。他可以选择以下的方式击败对应的 Justin:

D_ _D J_ _J
_D D_ _D D_

故而 Justin 不可能赢。