#P18853. [Croatian CPC2024] Gladni Gargamel

[Croatian CPC2024] Gladni Gargamel

Gladni Gargamel

题目描述

饥饿的 Gargamel 想穿过一个 NN 行、MM 列的方格矩阵,去右下角寻找食物。每个格子是黑色或白色,左上角和右下角保证是黑色。

他从左上角出发。每一步必须向上、下、左或右移动到一个相邻格子,不能离开矩阵。如果移动后进入白色格子,他会立即被传送到矩阵中所有白色格子中等概率随机选择的一个,可能仍是当前格子。

每一步先移动,再至多发生一次传送。一次传送完成后,不会仅因落点是白色而继续传送;他需要先进行下一次相邻移动。

到达右下角时过程立即结束。如果每一步都采取最优策略,求到达终点所需步数的最小期望。

输入格式

第一行包含整数 TT(1≤T≤10001\le T\le1000),表示测试场景数。

每个场景的第一行包含两个整数 N,MN,M(1≤N,M≤10001\le N,M\le1000)。

接下来 NN 行,每行包含 MM 个字符。C 表示黑色格子,B 表示白色格子。

所有场景的 N×MN\times M 之和不超过 10610^6。

输出格式

对于每个场景,输出一行形如 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

样例解释

第一个样例的第一个场景中,所有格子都是黑色,可以直接走到右下角。

第二个场景中有两个白色格子,但无论传送到哪一个,都能在下一步到达右下角。