#P18849. [Croatian CPC2023] Ekstravagantni Eksperiment
[Croatian CPC2023] Ekstravagantni Eksperiment
Ekstravagantni Eksperiment
题目描述
Matija 正在观察一只白鼠。笼子的底部是一个 的方格,每个格子是白色或红色。行从上到下编号为 到 ,列从左到右编号为 到 。
白鼠每一步可以移动到与当前格子共边的一个格子,但它害怕红色,任何时刻都只能停留在白色格子上。
Matija 用一个覆盖 个格子的盒子罩住白鼠,盒子的边与方格的边平行。白鼠可以在盒子内部移动,这些移动从外面看不见。当白鼠位于盒子边缘,并向盒子外侧移动一格时,盒子也会沿同一方向移动一格,白鼠仍在盒子内。

图中黑色圆点表示白鼠,阴影区域表示盒子。
Matija 记录了盒子的初始位置,以及盒子的每一次移动:L、R、U、D 分别表示左、右、上、下。白鼠的初始位置未知,只知道它在盒子覆盖的白色格子中。
请根据这些记录,求白鼠最少可能走了多少步。
输入格式
第一行包含两个整数 ,满足 ,。
接下来 行,每行包含 个字符。小写字母 b 表示白色格子,小写字母 c 表示红色格子。
接下来一行包含整数 (),表示盒子初始覆盖区域左上角格子的行号和列号。
接下来一行包含整数 (),表示盒子的移动次数。
最后一行是长度为 的字符串,仅由 L、R、U、D 组成,按时间顺序给出盒子的移动方向。
输出格式
输出一个整数,表示白鼠最少可能走的步数。
样例输入 1
5 3
bbbbb
bcbcb
bbbbb
bcccb
bbbbb
3 3
2
LU
样例输出 1
3
样例输入 2
5 3
bbbbb
bbccb
bccbb
bbbbb
bbbbb
3 1
4
URRU
样例输出 2
10
样例输入 3
6 4
bbbbbc
bbbccc
bcbbbb
bccccb
bbbbcb
bbbbbb
1 1
4
DRUR
样例输出 3
18
样例解释
第二个样例中,白鼠可以从 出发,依次走:上、下、下、右、右、右、上、右、上、上,共 步。
第三个样例中,白鼠可以从 出发,依次走:下、上、上、上、右、右、下、右、右、左、左、上、上、下、下、右、右、右,共 步。