← 返回题目列表

AtCoder · awc0025_b

B. 仓库巡检机器人

中文机器翻译题面 查看原题

分数: 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, 1) 有一个包裹,已将其收集(该包裹已从该单元格中移除)。
  2. 对于 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