#P18849. [Croatian CPC2023] Ekstravagantni Eksperiment

[Croatian CPC2023] Ekstravagantni Eksperiment

Ekstravagantni Eksperiment

题目描述

Matija 正在观察一只白鼠。笼子的底部是一个 n×nn\times n 的方格,每个格子是白色或红色。行从上到下编号为 11 到 nn,列从左到右编号为 11 到 nn。

白鼠每一步可以移动到与当前格子共边的一个格子,但它害怕红色,任何时刻都只能停留在白色格子上。

Matija 用一个覆盖 k×kk\times k 个格子的盒子罩住白鼠,盒子的边与方格的边平行。白鼠可以在盒子内部移动,这些移动从外面看不见。当白鼠位于盒子边缘,并向盒子外侧移动一格时,盒子也会沿同一方向移动一格,白鼠仍在盒子内。

第一个样例的示意图

图中黑色圆点表示白鼠,阴影区域表示盒子。

Matija 记录了盒子的初始位置,以及盒子的每一次移动:L、R、U、D 分别表示左、右、上、下。白鼠的初始位置未知,只知道它在盒子覆盖的白色格子中。

请根据这些记录,求白鼠最少可能走了多少步。

输入格式

第一行包含两个整数 n,kn,k,满足 2≤k≤102\le k\le10,k<n≤100k<n\le100。

接下来 nn 行,每行包含 nn 个字符。小写字母 b 表示白色格子,小写字母 c 表示红色格子。

接下来一行包含整数 r,sr,s(1≤r,s≤n−k+11\le r,s\le n-k+1),表示盒子初始覆盖区域左上角格子的行号和列号。

接下来一行包含整数 pp(1≤p≤1061\le p\le10^6),表示盒子的移动次数。

最后一行是长度为 pp 的字符串,仅由 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

样例解释

第二个样例中,白鼠可以从 (3,1)(3,1) 出发,依次走:上、下、下、右、右、右、上、右、上、上,共 1010 步。

第三个样例中,白鼠可以从 (4,1)(4,1) 出发,依次走:下、上、上、上、右、右、下、右、右、左、左、上、上、下、下、右、右、右,共 1818 步。