← 返回题目列表

Codeforces · 1607/E

E. 板上机器人 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$$$)——机器人所在场地的高度和宽度。描述的第二行是一个字符串 $$$s$$$,仅由字符“L”、“R”、“D”和“U”组成——机器人执行的命令序列。该字符串的长度从 $$$1$$$ 到 $$$10^6$$$ 命令。

保证所有测试用例$$$s$$$的总长度不超过$$$10^6$$$。

输出

打印 $$$t$$$ 行,每行都包含相应测试用例的答案。测试用例的答案是两个整数 $$$r$$$ ($$$1 \leq r \leq n$$$) 和 $$$c$$$ ($$$1 \leq c \leq m$$$),用空格分隔 - 机器人应开始移动以执行尽可能多的命令的单元格坐标(行号和列号)。

如果有多个这样的单元格,则可以输出其中任何一个。

示例

输入 #1

4
1 1
L
1 2
L
3 3
RRDLUU
4 3
LUURRDDLLLUU

输出 #1

1 1
1 2
2 1
3 2