题目描述

我们有一个网格，包含 $H$ 行和 $W$ 列。$(i,j)$ 表示从上往下数第 $i$ 行、第 $j$ 列的方格。 $(i,j)$ 上写有字符 $G_{i,j}$，其中 $G_{i,j}$ 可以是 U、D、L 或 R。

你最初位于 $(1,1)$。你将重复执行以下操作，直到无法继续移动。

• 假设你当前所在的方格是 $(i,j)$。

• 如果 $G_{i,j}$ 是 U 且 $i \neq 1$，则移动到 $(i-1,j)$。

• 如果 $G_{i,j}$ 是 D 且 $i \neq H$，则移动到 $(i+1,j)$。

• 如果 $G_{i,j}$ 是 L 且 $j \neq 1$，则移动到 $(i,j-1)$。

• 如果 $G_{i,j}$ 是 R 且 $j \neq W$，则移动到 $(i,j+1)$。

• 否则，无法继续移动。

当你无法再继续移动时，打印你最终到达的方格。

如果你无法停止移动并无限次地移动，请打印 -1。

输入格式

第一行输入 $H$ $W$

接下来 $H$ 行每行输入 $W$ 个字符，代表 $G_{i,j}$

输出格式

当你无法再继续移动时，打印你最终到达的方格 $(i,j)$。如果你无法停止移动并无限次地移动，请打印 -1。

2 3
RDU
LRU

1 3

2 3
RRD
ULL

-1

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

9 5

提示

数据范围

• $1\ \leq\ H,\ W\ \leq\ 500$
• $G_{i,j}$ 是 U, D, L, R 中的一种。
• $H,\ W$ 都是整数。

样例 1 解释

你将按如下顺序移动：$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$，最终停在 $(1, 3)$，因此答案是 $(1, 3)$。

样例 2 解释

你将无限次地重复以下移动：$(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots$，因此在这种情况下应该打印 -1。