

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
縦 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 RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR
出力例 3
9 5
Score : 300 points
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} isU
and i \neq 1, move to (i-1,j).
If G_{i,j} isD
and i \neq H, move to (i+1,j).
If G_{i,j} isL
and j \neq 1, move to (i,j-1).
If G_{i,j} isR
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
, orR
. - 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