CF1607E Robot on the Board 1

有一个机器人位于一个 $n \times m$ 的棋盘上（$n$ 行 $m$ 列）。棋盘的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。 机器人可以从当前位置移动到四个相邻的格子之一。 给定机器人要执行的指令序列 $s$。每条指令用 'L'、'R'、'D' 或 'U' 表示，分别代表向左、向右、向下或向上移动。 机器人可以从任意一个格子开始移动。机器人从第一条指令开始，严格按照 $s$ 中给出的顺序依次执行指令。如果机器人移动出了棋盘的边界，则会掉下去并损坏。导致机器人掉下去的那条指令不算作成功执行。 机器人的目标是在不掉下棋盘的前提下，尽可能多地执行指令。例如，在 $3 \times 3$ 的棋盘上，如果机器人从中心格子开始执行 $s=$ "RRDLUU"（右、右、下、左、上、上），则机器人会执行一条指令，下一条指令会让它越过边界。如果机器人从 $(2, 1)$（第二行第一列）开始移动，则所有指令都能成功执行，最终停在 $(1, 2)$（第一行第二列）。  机器人从 $(2, 1)$（第二行第一列）开始。它依次向右、右、下、左、上、上移动。最终停在 $(1, 2)$（第一行第二列）。请你确定机器人应从哪个格子开始移动，才能执行尽可能多的指令。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 接下来的 $2t$ 行描述每个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^6$），分别表示棋盘的高度和宽度。第二行是一个只包含 'L'、'R'、'D' 和 'U' 的字符串 $s$，表示机器人要执行的指令序列。字符串长度为 $1$ 到 $10^6$。 保证所有测试用例中 $s$ 的总长度不超过 $10^6$。

输出 $t$ 行，每行包含两个整数 $r$ 和 $c$（$1 \leq r \leq n$，$1 \leq c \leq m$），表示机器人应从哪个格子（行号和列号）开始移动，才能执行尽可能多的指令。 如果有多个满足条件的格子，可以输出其中任意一个。

由 ChatGPT 4.1 翻译