分数: 200 点
问题陈述
有一个网格 H 行和 W 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
If S_{i,j} is #,单元格 (i,j) 无法通行;如果是的话 .,该小区可通行且不含房屋;如果是的话 @,该牢房可以通过并且包含一座房子。
最初,圣诞老人在牢房里 (X,Y)。他会按照弦来行动 T 如下。
- 让 |T| 是字符串的长度 T。对于 i=1,2,\ldots,|T|,他的动作如下。
- 让 (x,y) 是他当前所在的牢房。
- If T_i is
U和细胞 (x-1,y) 还可以,移至单元格 (x-1,y). - If T_i is
D和细胞 (x+1,y) 还可以,移至单元格 (x+1,y). - If T_i is
L和细胞 (x,y-1) 还可以,移至单元格 (x,y-1). - If T_i is
R和细胞 (x,y+1) 还可以,移至单元格 (x,y+1). - 否则,留在牢房里 (x,y).
- If T_i is
- 让 (x,y) 是他当前所在的牢房。
找到他完成所有动作后所在的牢房,以及他在动作过程中经过或到达的不同房屋的数量。如果同一栋房子经过多次,只算一次。
约束
- 3 \leq H,W \leq 100
- 1 \leq X \leq H
- 1 \leq Y \leq W
- 所有给定的数字都是整数。
- 每个 S_{i,j} 是其中之一
#,.,@. - S_{i,1} 和 S_{i,W} 是
#对于每个 1 \leq i \leq H. - S_{1,j} 和 S_{H,j} 是
#对于每个 1 \leq j \leq W. - S_{X,Y}=
. - T 是长度至少为 1 最多 10^4,包括
U,D,L,R.
输入
输入由标准输入按以下格式给出:
H W X Y
S_{1,1}S_{1,2}\ldots S_{1,W}
\dots
S_{H,1}S_{H,2}\ldots S_{H,W}
T
输出
让 (X,Y) 是完成所有操作后他所在的单元格,并且 C 是他在行动期间经过或到达的不同房屋的数量。打印 X,Y,C 按此顺序用空格分隔。
示例输入 1
5 5 3 4 ##### #...# #.@.# #..@# ##### LLLDRUU
示例输出 1
2 3 1
圣诞老人的行为如下:

- T_1=
L,所以他从 (3,4) to (3,3)。一座房子过去了。 - T_2=
L,所以他从 (3,3) to (3,2). - T_3=
L,但是单元格 (3,1) 无法通行,所以他留在 (3,2). - T_4=
D,所以他从 (3,2) to (4,2). - T_5=
R,所以他从 (4,2) to (4,3). - T_6=
U,所以他从 (4,3) to (3,3)。一座房子过去了,但它已经过去了。 - T_7=
U,所以他从 (3,3) to (2,3).
他的行动中经过或到达的房屋数量为 1.
示例输入 2
6 13 4 6 ############# #@@@@@@@@@@@# #@@@@@@@@@@@# #@@@@.@@@@@@# #@@@@@@@@@@@# ############# UURUURLRLUUDDURDURRR
示例输出 2
3 11 11
示例输入 3
12 35 7 10 ################################### #.................................# #..........@......................# #......@................@.........# #.............##............@.....# #...##........##....##............# #...##........##....##.......##...# #....##......##......##....##.....# #....##......##......##..##.......# #.....#######.........###.........# #.................................# ################################### LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU
示例输出 3
4 14 1