巡逻 - 代码源竞赛平台

题目描述

一辆小车正在会场内进行试运行，需要统计它到过的不同位置数量。

会场可以看作一个 hh 行 ww 列的网格，行从上到下编号为 11 到 hh，列从左到右编号为 11 到 ww。每个格子是空地或障碍，分别用字符 . 和 # 表示。

小车最初位于空地 (r,c)(r,c)。接下来，小车将从左到右依次执行字符串 ss 中的 qq 条指令。

设小车当前位于 (x,y)(x,y)，其中 xx 表示行号，yy 表示列号。四种指令的含义如下：

  • U：尝试向上移动一格，目标位置为 (x−1,y)(x-1,y)。
  • D：尝试向下移动一格，目标位置为 (x+1,y)(x+1,y)。
  • L：尝试向左移动一格，目标位置为 (x,y−1)(x,y-1)。
  • R：尝试向右移动一格，目标位置为 (x,y+1)(x,y+1)。

每次执行指令时，若目标格子在网格内且为空地，小车就移动到该格子；否则，小车留在原地，并继续执行下一条指令。

请统计执行完所有指令后，小车一共到过多少个不同的格子。初始位置也计入其中，同一个格子无论到过多少次，都只计数一次。

输入格式

第一行包含三个整数 h,w,qh,w,q，分别表示网格的行数、列数和指令数。

第二行包含两个整数 r,cr,c，表示小车初始位置的行号和列号。

接下来 hh 行，第 ii 行包含一个长度为 ww 的字符串 gig_i，表示网格的第 ii 行。其中，. 表示空地，# 表示障碍。

最后一行包含一个长度为 qq 的字符串 ss，表示依次执行的指令，只含字符 U、D、L、R。

输出格式

输出一个整数，表示小车到过的不同格子数量。

样例

3 4 9
2 1
....
.#..
....
RRDDRRUUL

7

1 1 4
1 1
.
UDLR

1

样例解释

对于样例 11，前两条向右的指令均被障碍阻止。随后，小车向下移动到 (3,1)(3,1)，再一次尝试向下移动时因越界而留在原地。之后，小车依次到达 (3,2)(3,2)、(3,3)(3,3)、(2,3)(2,3)、(1,3)(1,3)、(1,2)(1,2)。计入初始位置 (2,1)(2,1)，一共到过 77 个不同的格子。

对于样例 22，四条指令的目标位置都在网格外，小车始终留在初始位置，因此答案为 11。

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 100%100\% 的数据，1≤h,w≤501\le h,w\le 50，1≤q≤2×1051\le q\le 2\times 10^5，1≤r≤h1\le r\le h，1≤c≤w1\le c\le w。每个 gig_i 的长度为 ww，且只含字符 . 和 #；grg_r 的第 cc 个字符为 .。ss 的长度为 qq，且只含字符 U、D、L、R。