Belt Conveyor

题目描述

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

输入格式

输入从标准输入给出，格式如下： $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$。

2 3
RDU
LRU

1 3

2 3
RRD
ULL

-1

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

9 5

提示

$1 \leq H, W \leq 500$ $G_{i,j}$ 是 $U$、$D$、$L$ 或 $R$。 $H$ 和 $W$ 为整数。你会按 $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3)$ 移动，最终停在这里，所以答案是 $(1, 3)$。
你会无限地重复移动，路径为 $(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$。

标签: AtCoder|abc265C

来源

AtCoder|abc265C