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$ 的格子）都是海洋。 Takahashi 的飞船在某个格子坠毁。之后，他按照由长度为 $N$ 的字符串 $T$ 表示的指令在网格上移动了 $N$ 次，字符串 $T$ 由 $L$、$R$、$U$、$D$ 组成。对于 $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

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

6

提示

$H$, $W$ 和 $N$ 是整数。 $3 \leq H, W \leq 500$ $1 \leq N \leq 500$ $T$ 是由 $L$、$R$、$U$、$D$ 组成的长度为 $N$ 的字符串。 $S_i$ 是由 $.$ 和 # 组成的长度为 $W$ 的字符串。 至少存在一个格子可能是 Takahashi 的当前所在位置。 网格的所有边界格子都是海洋。以下两种情况是可能的，因此可能是 Takahashi 当前所在位置的格子有两个：$(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)$。

标签: AtCoder|abc341C

来源

AtCoder|abc341C