AT_abc341_c.[ABC341C] Takahashi Gets Lost

有一个 $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 表示向左移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i, j-1)$。
• R 表示向右移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i, j+1)$。
• U 表示向上移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i-1, j)$。
• D 表示向下移动 $1$ 格。即，若移动前在 $(i, j)$，则移动后在 $(i+1, j)$。

已知高桥君移动路径上的所有格子（包括降落点和当前所在格子）都不是海洋。请输出高桥君当前可能所在的格子的个数。

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

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

请输出答案。

限制条件

• $H,\ W,\ N$ 为整数。
• $3 \leq H,\ W \leq 500$。
• $1 \leq N \leq 500$。
• $T$ 是只包含 L、R、U、D 的长度为 $N$ 的字符串。
• $S_i$ 是只包含 . 和 # 的长度为 $W$ 的字符串。
• 至少存在 $1$ 个格子可能是高桥君当前所在的位置。
• 网格的外周格子全部是海洋。

样例解释 1

由于存在以下两种情况，高桥君当前可能所在的格子为 $(3,4)$ 和 $(4,5)$，共 $2$ 个。

• 在 $(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)$。

由 ChatGPT 4.1 翻译