高桥君迷路了

题目描述

有一个 $H$ 行 $W$ 列的网格。

网格的每个格子是陆地或海洋，由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 表示。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子；若 $S_i$ 的第 $j$ 个字符是 .，则 $(i, j)$ 是陆地；若该字符是 #，则 $(i, j)$ 是海洋。

数据保证网格边界上的所有格子（即满足 $i = 1$、$i = H$、$j = 1$、$j = W$ 中至少一个条件的格子 $(i, j)$）都是海洋。

高桥君的飞船坠落在了网格中的某个格子上。之后，他按照由 L、R、U、D 组成、长度为 $N$ 的指令字符串 $T$，在网格上移动了 $N$ 次。对 $i = 1, 2, \ldots, N$，$T$ 的第 $i$ 个字符表示第 $i$ 次移动，具体含义如下：

• L 表示向左移动一格。即移动前在 $(i, j)$ 的话，移动后在 $(i, j-1)$。
• R 表示向右移动一格。即移动前在 $(i, j)$ 的话，移动后在 $(i, j+1)$。
• U 表示向上移动一格。即移动前在 $(i, j)$ 的话，移动后在 $(i-1, j)$。
• D 表示向下移动一格。即移动前在 $(i, j)$ 的话，移动后在 $(i+1, j)$。

已知他经过的所有格子（包括坠落的格子和当前所在的格子）都不是海洋。输出可能是他当前位置的格子的数量。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$ $N$
$T$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

输出答案。

样例

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

2

以下是两种可能的情况，因此可能是高桥当前位置的格子有 2 个：$(3, 4)$ 和 $(4, 5)$。

• 他在格子 $(3, 5)$ 坠落，并移动 $(3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$。
• 他在格子 $(4, 6)$ 坠落，并移动 $(4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5)$。

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

6

数据范围

• $H$、$W$、$N$ 均为整数
• $3 \le H, W \le 500$
• $1 \le N \le 500$
• $T$ 是由 L、R、U、D 组成的长度为 $N$ 的字符串
• $S_i$ 是由 . 和 # 组成的长度为 $W$ 的字符串
• 至少存在一个格子可能是高桥君当前的位置
• 网格边界上的所有格子都是海洋