102652: [AtCoder]ABC265 C - Belt Conveyor

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. $(i, j)$ denotes the square at the $i$-th row from the top and $j$-th column from the left.
$(i,j)$ has a character $G_{i,j}$ written on it. $G_{i,j}$ is U, D, L, or R.

You are initially at $(1,1)$. You repeat the following operation until you cannot make a move.

Let $(i,j)$ be the square you are currently at.
If $G_{i,j}$ is U and $i \neq 1$, move to $(i-1,j)$.
If $G_{i,j}$ is D and $i \neq H$, move to $(i+1,j)$.
If $G_{i,j}$ is L and $j \neq 1$, move to $(i,j-1)$.
If $G_{i,j}$ is R and $j \neq W$, move to $(i,j+1)$.
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

• $1 \leq H, W \leq 500$
• $G_{i,j}$ is U, D, L, or R.
• $H$ and $W$ are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$
$G_{1,1}G_{1,2}\dots G_{1,W}$
$G_{2,1}G_{2,2}\dots G_{2,W}$
$\vdots$
$G_{H,1}G_{H,2}\dots G_{H,W}$

Output

If you end up at $(i, j)$, print it in the following format:

$i$ $j$

If you indefinitely repeat moving, print -1.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$, ending up here, so the answer is $(1, 3)$.

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as $(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$, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

问题描述

我们有一个有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。

约束

• $1 \leq H, W \leq 500$
• $G_{i,j}$是U、D、L或R。
• $H$和$W$是整数。

输入

输入通过标准输入以以下格式给出：

$H$ $W$
$G_{1,1}G_{1,2}\dots G_{1,W}$
$G_{2,1}G_{2,2}\dots G_{2,W}$
$\vdots$
$G_{H,1}G_{H,2}\dots G_{H,W}$

输出

如果你最后在$(i, j)$，以以下格式输出：

$i$ $j$

如果你无限重复移动，则输出-1。

样例输入1

2 3
RDU
LRU

样例输出1

1 3

你将移动到$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$，最后到达这里，所以答案是$(1, 3)$。

样例输入2

2 3
RRD
ULL

样例输出2

-1

你将无限重复移动到$(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。

样例输入3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

样例输出3

9 5