[ABC385B] Santa Claus 1

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

• 如果 $S_{i,j}$ 是 #，该格子不可通行。
• 如果 $S_{i,j}$ 是 .，该格子可通行且没有房子。
• 如果 $S_{i,j}$ 是 @，该格子可通行且有房子。

圣诞老人初始在格子 $(X, Y)$。他将按照长度为 $|T|$ 的字符串 $T$ 依次行动，对于 $i = 1, 2, \ldots, |T|$，行动规则如下：

• 当前所在格子为 $(x, y)$。
• 若 $T_i$ 为 U 且 $(x-1, y)$ 可通行，则移动到 $(x-1, y)$；
• 若 $T_i$ 为 D 且 $(x+1, y)$ 可通行，则移动到 $(x+1, y)$；
• 若 $T_i$ 为 L 且 $(x, y-1)$ 可通行，则移动到 $(x, y-1)$；
• 若 $T_i$ 为 R 且 $(x, y+1)$ 可通行，则移动到 $(x, y+1)$；
• 否则，停留在 $(x, y)$。

在所有行动完成后，请输出他最终所在的格子，以及在整个行动过程中经过或到达过的不同房子的数量。如果同一房子被多次经过，只计一次。

输入格式

输入通过标准输入给出，格式如下：

H W
X Y
S_{1,1}S_{1,2}...S_{1,W}
...
S_{H,1}S_{H,2}...S_{H,W}
T

输出格式

设最终所在格子为 $(X, Y)$，经过的不同房子数量为 $C$，则按照 X Y C 的顺序，用空格分隔输出。

样例

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

2 3 1

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

3 11 11

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

4 14 1

数据范围

• $3 \le H, W \le 100$
• $1 \le X \le H$，$1 \le Y \le W$
• 所有数字均为整数。
• $S_{i,j}$ 为 #、. 或 @ 之一。
• 网格的边界（$S_{i,1}$、$S_{i,W}$、$S_{1,j}$、$S_{H,j}$）始终为 #（地图被墙壁包围）。
• 初始位置 $S_{X,Y} =$ .（没有房子）。
• $T$ 的长度 $|T|$ 满足 $1 \le |T| \le 10^4$，且仅由 U、D、L、R 组成。