You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个$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)$）全部为海洋。

小Z乘坐的宇宙飞船在网格的某个方格上紧急着陆。之后，小Z按照仅由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)$。

已知小Z的移动路径上的方格（包括紧急着陆的方格和当前所在的方格）都不是海洋。请输出小Z当前可能所在的方格数量。

输入格式

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

输出格式

移动的方格数

样例 #1

样例输入 #1

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

样例输出 #1

2

样例 #2

样例输入 #2

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

样例输出 #2

6

提示

数据范围

• $H$、$W$、$N$ 均为整数
• $3 \leq H$，$W \leq 500$
• $1 \leq N \leq 500$
• $T$ 是仅由 L、R、U、D 组成的长度为 $N$ 的字符串
• $S_i$ 是仅由 . 和 # 组成的长度为 $W$ 的字符串
• 小Z当前可能所处的方格至少有1个。
• 网格外周的方格均为海洋。

样例解释

存在以下两种可能情况，所以小Z现在可能所处的方格为$(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)$移动的情况。