分数: 266 分
问题陈述
高桥以网格形式管理仓库 H 行和 W 列。牢房位于 i从顶部算起的第行 (1 \leq i \leq H) 和 j左起第 列 (1 \leq j \leq W) 表示为单元格 (i, j)。每个单元格上要么放置有包裹,要么是空的。仓库的状态表示为 H 字符串 S_1, S_2, \ldots, S_H,每个长度 W。如果 j- 第一个字符 S_i is #,然后是单元格 (i, j) 有一个包裹;如果是的话 .,单元格为空。
高桥计划在该仓库引入一台检查机器人,并让它通过移动来收集包裹。机器人最初放置在单元内 (1, 1) (左上角)。
机器人给出 N 指令按顺序排列,用字符串表示 T 长度 N。的 k- 第一个字符 T (1 \leq k \leq N) 对应于 k第一条指令,每条指令都是以下指令之一:
U:上移一个单元格(行数减少 1)D:向下移动一个单元格(行号增加 1)L:向左移动一个单元格(列数减少 1)R:右移一个单元格(列号增加 1)
但是,如果指令的目的地位于网格之外,则该指令将被忽略,并且机器人将保持在当前位置。
机器人操作如下:
- 机器人被放置在单元格 (1, 1)。如果细胞 (1, 1) 有一个包裹,已将其收集(该包裹已从该单元格中移除)。
- 对于 k = 1, 2, \ldots, N 按顺序, 执行 k第一条指令。在处理完每条指令后(无论是机器人移动还是指令被忽略而机器人留在原地),如果机器人所在的单元格上有包裹,则将其收集(包裹从该单元格中移除)。
如果机器人重新访问已经收集过包裹的单元格,则不会发生任何事情。
确定执行所有指令后仓库中剩余的包裹数量。
约束
- 1 \leq H \leq 500
- 1 \leq W \leq 500
- 1 \leq N \leq 2 \times 10^5
- H, W, N 是整数
- S_i 是一个长度为 W 仅包含
#和. - T 是一个长度为 N 仅包含
U,D,L,R
输入
H W N S_1 S_2 \vdots S_H T
- 第一行包含行数 H,列数 W,以及指令数量 N,用空格分隔。
- 的 2-nd 通过 (H + 1)第行包含字符串 S_i (1 \leq i \leq H) 代表仓库的状态。
- S_i 是一个长度为 W,其中 j- 第一个字符是
#表示单元格 (i, j) 有一个包裹,并且.表示它是空的。 - 的 (H + 2)- 第行包含字符串 T 长度 N 代表给机器人的指令。
- T 仅包含
U,D,L,R.
输出
在一行上打印执行所有指令后仓库中剩余的包裹数量。
示例输入 1
3 4 9 #..# .##. ..#. RRDDLUUUL
示例输出 1
1
示例输入 2
2 3 8 ### ..# UUURRRDD
示例输出 2
0
示例输入 3
6 7 30 .#..#.. ##...#. ..#.#.. .##.... ...###. #..#..# RRRDDRULDLURRRDDLLUUURRDDDLURD
示例输出 3
10
示例输入 4
12 15 60 #..#...##....#. .#....#....##.. ....##..#...#.. ###...#..#..... ..#..#..##..#.. .....#.....#..# .##..#..#..##.. ...#.....##.... #....###...#... ..##..#....#..# .#...#..#..#... ...#..##.....#. RRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUURRRDDLLUUUR
示例输出 4
46
示例输入 5
1 1 12 # UDLRUDLRUDLR
示例输出 5
0