小明自己发明了一个电子的滑冰游戏如下:
初始时给你一个大小为 n×n 的地图,地图由#、*、数字符号(0至9)组成,其中地图的边界一定都是#,且#只出现在边界。
下图是一个 n = 7n=7 的例子:
#######
#12345#
#4**12#
#67*27#
#*08*1#
#11129#
####### 定义坐标 (a, b) 为第 a 行第 b 列。
#代表不可破坏的墙壁,*代表可敲碎的冰块,而数字和得分有关。
游戏开始时,游戏会随机告诉你游戏角色所在的起始位置。接著每一步有 2 种可能操作:
第一种是滑行的操作。可以选择上下左右四个方向的任一个方向滑行,一但滑行开始后,只当碰到墙壁或是冰块时才会停下来。若选择的方向的下一格就是墙壁或是冰块,就会留在原地。滑行完后,游戏的得分就会增加滑行完后游戏角色停下的格子上的数字,增加完后此数字会变为0。
第二种操作是敲碎冰块的操作。此操作只能在上一步是滑行且挡住游戏角色的是冰块而不是墙壁时执行,执行后,上一步挡住游戏角色的冰块就会被敲碎,之后此冰块的位置会变为数字0的格子。
设计玩此游戏后小明超想知道,若游戏角色起始位置在座标 (x, y),且只能移动恰 m 步,游戏结束时最多能得多少分。
但这问题实在太难了,于是小明先拜託你帮忙写一个程序,模拟小明所执行的操作并计算游戏结束时的总得分。其中,向上下左右四个方向滑行的操作依序用大写英文字母U,D,L,R表示;而敲碎冰块的操作由大写英文字母B表示。保证当执行敲碎冰块操作时,上一步一定是滑行且在上一步挡住游戏角色的一定冰块。
输入格式 输入第一行包含一个正整数 n,代表地图大小。
接着有 nn 行,每行有一个长度为 n 的字串,这 n 行代表著游戏的地图。
下一行有两个正整数 x,y,代表游戏角色起始位置在 (x, y)。
再下一行有一个正整数 m,代表你要模拟的操作次数。
之后还有一行,包含长度为 m 的由大写英文字母组成的字串,此字串的第 i 个字母代表你要模拟的第 i 个操作。
输出格式 输出包含一行,包含一个整数。代表按照输入的操作模拟时,游戏结束后的得分。
数据范围 对于 50%50% 的数据,模拟的操作中 不包含 敲碎冰块的操作。
对于所有 试数据都满足 3≤n≤20,1≤m≤500,起始位置一定是数字的格子。
输出时每行末尾的多余空格,不影响答案正确性
要求使用「文件输入输出」的方式解题,输入文件为 game.in,输出文件为 game.out
样例输入
7
#######
#12345#
#4**12#
#67*27#
#*08*1#
#11129#
#######
2 4
5
DDRUL
样例输出
9