#P18853. [Croatian CPC2024] Gladni Gargamel
[Croatian CPC2024] Gladni Gargamel
Gladni Gargamel
题目描述
饥饿的 Gargamel 想穿过一个 行、 列的方格矩阵,去右下角寻找食物。每个格子是黑色或白色,左上角和右下角保证是黑色。
他从左上角出发。每一步必须向上、下、左或右移动到一个相邻格子,不能离开矩阵。如果移动后进入白色格子,他会立即被传送到矩阵中所有白色格子中等概率随机选择的一个,可能仍是当前格子。
每一步先移动,再至多发生一次传送。一次传送完成后,不会仅因落点是白色而继续传送;他需要先进行下一次相邻移动。
到达右下角时过程立即结束。如果每一步都采取最优策略,求到达终点所需步数的最小期望。
输入格式
第一行包含整数 (),表示测试场景数。
每个场景的第一行包含两个整数 ()。
接下来 行,每行包含 个字符。C 表示黑色格子,B 表示白色格子。
所有场景的 之和不超过 。
输出格式
对于每个场景,输出一行形如 a/b 的最简分数,表示所求期望。其中分母为正数,分子和分母互质。
样例输入 1
3
2 2
CC
CC
2 2
CB
BC
1 12
CBCCCCCCCCBC
样例输出 1
2/1
2/1
4/1
样例输入 2
1
6 2
CC
CC
CC
CC
CC
CC
样例输出 2
6/1
样例输入 3
1
6 3
CBC
CBC
CBC
CBC
CBC
CBC
样例输出 3
4/1
样例解释
第一个样例的第一个场景中,所有格子都是黑色,可以直接走到右下角。
第二个场景中有两个白色格子,但无论传送到哪一个,都能在下一步到达右下角。