分数: 250 点
问题陈述
有一个网格 H 行和 W 列。
网格的每个单元格是 土地 or 海,表示为 H 字符串 S_1, S_2, \ldots, S_H 长度 W。让 (i, j) 表示位于 i从顶部开始的第行和 j从左边算起第 3 列,以及 (i, j) 是土地,如果
如果字符是 j- 第一个字符 S_i is .,和 (i, j) 是海 #.
约束保证网格周边的所有单元格(即单元格 (i, j) 满足至少一项 i = 1, i = H, j = 1, j = W)是大海。
高桥的宇宙飞船坠毁在网格中的一个单元格上。后来他搬家了
按照字符串表示的指令在网格上 N 次 T 长度 N 组成 L, R, U,和 D。对于 i = 1, 2, \ldots, N, i- 第一个字符 T 描述了 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 是整数。
- 3 \leq H, W \leq 500
- 1 \leq N \leq 500
- T 是一个长度为的字符串 N 组成
L,R,U,和D. - S_i 是一个长度为的字符串 W 组成
.和#. - 至少有一个单元格可能是高桥的当前位置。
- 网格周边的所有单元格都是海洋。
输入
输入由标准输入按以下格式给出:
H W N T S_1 S_2 \vdots S_H
输出
打印答案。
示例输入 1
6 7 5 LULDR ####### #...#.# ##...## #.#...# #...#.# #######
示例输出 1
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).
示例输入 2
13 16 9 ULURDLURD ################ ##..##.#..####.# ###.#..#.....#.# #..##..#####.### #...#..#......## ###.##.#..#....# ##.#####....##.# ###.###.#.#.#..# ######.....##..# #...#.#.######.# ##..###..#..#.## #...#.#.#...#..# ################
示例输出 2
6