Grid Walk

题目描述

有一个 $H$ 行 $W$ 列的网格。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子。 如果 $C_{i, j}$ 为 $.$ 则格子 $(i, j)$ 是空的；如果为 # 则不是空的。 Takahashi 现在在格子 $(S_i, S_j)$，他将按以下规则依次对 $i = 1, 2, \ldots, |X|$ 执行操作。

如果 $X$ 的第 $i$ 个字符是 $L$，且他当前格子左边的格子存在且是空的，他就移到左边的格子。否则，他停留在当前格子。 如果 $X$ 的第 $i$ 个字符是 $R$，且他当前格子右边的格子存在且是空的，他就移到右边的格子。否则，他停留在当前格子。 如果 $X$ 的第 $i$ 个字符是 $U$，且他当前格子上方的格子存在且是空的，他就移到上方的格子。否则，他停留在当前格子。 如果 $X$ 的第 $i$ 个字符是 $D$，且他当前格子下方的格子存在且是空的，他就移到下方的格子。否则，他停留在当前格子。

在完成这一系列操作后，输出他所在的格子。

输入格式

输入按下列格式由标准输入给出： $H$ $W$ $S_i$ $S_j$ $C_{1, 1}$$C_{1, 2}$$\ldots$$C_{1, W}$ $C_{2, 1}$$C_{2, 2}$$\ldots$$C_{2, W}$ $\vdots$ $C_{H, 1}$$C_{H, 2}$$\ldots$$C_{H, W}$ $X$

输出格式

令 $(x, y)$ 为 Takahashi 在完成这一系列操作后所在的格子。输出 $x$ 和 $y$，用空格分隔。

2 3
2 1
.#.
...
ULDRU

2 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

2 4

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

1 1

提示

$1 \leq H, W \leq 50$ $1 \leq S_i \leq H$ $1 \leq S_j \leq W$ $H, W, S_i, S_j$ 是整数。 $C_{i, j}$ 为 $.$ 或 #。 $C_{S_i, S_j} =$ $.$ $X$ 是长度在 $1$ 到 $50$（含）之间的字符串，由 $L$, $R$, $U$, $D$ 组成。Takahashi 从格子 $(2, 1)$ 开始。他的操作序列如下：

$X$ 的第 1 个字符是 $U$，且 $(2, 1)$ 上方的格子存在且是空的，所以他移到上方的格子，即 $(1, 1)$。 $X$ 的第 2 个字符是 $L$，且 $(1, 1)$ 左边的格子不存在，所以他停留在 $(1, 1)$。 $X$ 的第 3 个字符是 $D$，且 $(1, 1)$ 下方的格子存在且是空的，所以他移到下方的格子，即 $(2, 1)$。 $X$ 的第 4 个字符是 $R$，且 $(2, 1)$ 右边的格子存在且是空的，所以他移到右边的格子，即 $(2, 2)$。 $X$ 的第 5 个字符是 $U$，且 $(2, 2)$ 上方的格子存在但不是空的，所以他停留在 $(2, 2)$。

因此，完成操作序列后，他在格子 $(2, 2)$。

标签: AtCoder|abc364B

来源

AtCoder|abc364B