CF1607F Robot on the Board 2

有一个机器人位于一个 $n \times m$ 的棋盘上（$n$ 行，$m$ 列）。棋盘的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。 机器人可以从当前位置移动到四个相邻的格子之一。 每个格子上写有一个符号 'L'、'R'、'D' 或 'U'，分别表示机器人进入该格子后会向左、右、下或上移动。 机器人可以选择任意一个格子作为起点。然后，每一步都按照当前格子上的指令移动到相邻的格子。 - 如果机器人移动出了棋盘边界，则会掉下去并损坏。 - 如果机器人再次进入已经访问过的格子，则会损坏（此时停止移动）。 机器人可以选择任意一个格子作为起点。它的目标是在损坏或停止之前，尽可能多地移动。 请你确定机器人应从哪个格子出发，才能执行最多的指令。一次指令被认为成功执行，是指机器人从写有该指令的格子出发移动了一步（无论是移动到另一个格子还是掉出棋盘）。

第一行包含一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。 每个测试用例前有一个空行。接下来一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2000$；$1 \le m \le 2000$），表示棋盘的高度和宽度。接下来有 $n$ 行，每行恰好 $m$ 个字母，表示棋盘的第 $i$ 行。每个字母都是 'L'、'R'、'D' 或 'U'。 保证所有测试用例中所有棋盘的格子总数不超过 $4 \cdot 10^6$。

对于每个测试用例，输出三个整数 $r$、$c$ 和 $d$（$1 \le r \le n$；$1 \le c \le m$；$d \ge 0$），表示机器人应从第 $r$ 行第 $c$ 列的格子出发，最多可以移动 $d$ 步。如果有多组答案，输出任意一组即可。

由 ChatGPT 4.1 翻译