← 返回题目列表

AtCoder · abc265_c

F. 带式输送机

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列。 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
(i,j) 有一个字符 上面写着 G_{i,j} 。 G_{i,j} is U, D, L,或 R.

您最初位于 (1,1)。 重复以下操作,直到无法移动为止。

让 (i,j) 是您当前所在的方块。
If G_{i,j} is U 和 i \neq 1,移至 (i-1,j).
If G_{i,j} is D 和 i \neq H,移至 (i+1,j).
If G_{i,j} is L 和 j \neq 1,移至 (i,j-1).
If G_{i,j} is R 和 j \neq W,移至 (i,j+1).
否则,你无法移动。

打印当你无法移动时你最终到达的方格。
如果无限期地重复移动,则打印 -1 代替。

约束

  • 1 \leq H, W \leq 500
  • G_{i,j} is 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