AT_abc364_b.[ABC364B] Grid Walk

有一个 $H$ 行 $W$ 列的网格。网格中从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作格子 $(i,\,j)$。

当 $C_{i,\,j}$ 为 . 时，格子 $(i,\,j)$ 是空格子；为 # 时，则不是空格子。

高桥君现在位于格子 $(S_i,\,S_j)$，他会按照 $i=1,2,\ldots,|X|$ 的顺序，依次按照以下规则行动：

• 如果 $X$ 的第 $i$ 个字符为 L，且当前格子的左边有格子且该格子为空，则向左移动一格，否则留在原地。
• 如果 $X$ 的第 $i$ 个字符为 R，且当前格子的右边有格子且该格子为空，则向右移动一格，否则留在原地。
• 如果 $X$ 的第 $i$ 个字符为 U，且当前格子的上方有格子且该格子为空，则向上移动一格，否则留在原地。
• 如果 $X$ 的第 $i$ 个字符为 D，且当前格子的下方有格子且该格子为空，则向下移动一格，否则留在原地。

请输出高桥君完成所有行动后所在的格子 $(x,\,y)$，输出 $x$ 和 $y$，用空格分隔。

输入按以下格式从标准输入给出。

$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)$，输出 $x$ 和 $y$，用空格分隔。

限制条件

• $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$ 是由 L、R、U、D 组成的字符串，长度不少于 $1$ 且不超过 $50$

样例解释 1

高桥君一开始在格子 $(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)$。

由 ChatGPT 4.1 翻译