C - Belt Conveyor Editorial /

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} 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