9809: ABC265 —— C - Belt Conveyor
[Creator : ]
Description
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.
$(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.
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}$
```
```
$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`.
```
$i$ $j$
```
If you indefinitely repeat moving, print `-1`.
Constraints
- $1 \leq H, W \leq 500$
- $G_{i,j}$ is `U`, `D`, `L`, or `R`.
- $H$ and $W$ are integers.
- $G_{i,j}$ is `U`, `D`, `L`, or `R`.
- $H$ and $W$ are integers.
Sample 1 Input
2 3
RDU
LRU
Sample 1 Output
1 3
You will move as (1,1)→(1,2)→(2,2)→(2,3)→(1,3), ending up here, so the answer is (1,3).
Sample 2 Input
2 3
RRD
ULL
Sample 2 Output
-1
You will indefinitely repeat moving as (1,1)→(1,2)→(1,3)→(2,3)→(2,2)→(2,1)→(1,1)→(1,2)→…, so -1 should be printed in this case.
Sample 3 Input
9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR
Sample 3 Output
9 5