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$

输出格式

请输出答案。

输入输出样例 #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$ 的字符串。
• 至少存在 $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 翻译