CF1296C Yet Another Walking Robot

在一个坐标平面上有一个机器人。最初，机器人位于点 $(0, 0)$。它的移动路径由一个长度为 $n$ 的字符串 $s$ 描述，字符串仅包含字符 'L'、'R'、'U'、'D'。 每个字符对应如下移动： - 'L'（左）：表示机器人从点 $(x, y)$ 移动到点 $(x-1, y)$； - 'R'（右）：表示机器人从点 $(x, y)$ 移动到点 $(x+1, y)$； - 'U'（上）：表示机器人从点 $(x, y)$ 移动到点 $(x, y+1)$； - 'D'（下）：表示机器人从点 $(x, y)$ 移动到点 $(x, y-1)$。 制造该机器人的公司希望你对机器人的路径进行某种优化。为此，你可以从路径中删除任意一个非空子串。但公司不希望客户察觉到机器人的行为发生了变化。这意味着，优化前机器人最终停留在点 $(x_e, y_e)$，那么优化后（即从 $s$ 中删除某个子串后），机器人也必须最终停留在点 $(x_e, y_e)$。 由于预算有限，你需要删除最短的非空子串，使得优化后机器人的终点不变。如果无法进行这样的优化，则输出 -1。也有可能优化后路径为空串（即删除的子串就是整个 $s$）。 注意，$s$ 的子串是指可以通过从 $s$ 的前缀删除若干字符（可能为零）以及从后缀删除若干字符（可能为零）得到的字符串。例如，"LURLLR" 的子串有 "LU"、"LR"、"LURLLR"、"URL"，但没有 "RR" 和 "UL"。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 接下来的 $2t$ 行描述每个测试用例。每个测试用例包含两行。第一行是一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示机器人的路径长度。第二行是一个长度为 $n$ 的字符串 $s$，仅包含字符 'L'、'R'、'U'、'D'，表示机器人的路径。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$（$\sum n \le 2 \times 10^5$）。

对于每个测试用例，输出一行答案。如果无法删除某个非空子串使得机器人的终点不变，输出 -1。否则，输出两个整数 $l$ 和 $r$，表示你删除的子串的区间端点，满足 $1 \le l \le r \le n$。要求 $r-l+1$ 最小。如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译