← 返回题目列表

Codeforces · 1468/K

K. 机器人

中文机器翻译题面 查看原题

在四面无边的格子田上有一个机器人。最初,机器人位于坐标为 $$$(0, 0)$$$ 的单元格中。他将执行由大写拉丁字母“L”、“R”、“D”、“U”字符串描述的命令。当执行命令时,机器人只是朝相应的方向移动:

- 'L':向左一个单元格(当前单元格的 $$$x$$$ 坐标减少 $$$1$$$);
- 'R':向右移动一个单元格(当前单元格的 $$$x$$$ 坐标增加 $$$1$$$);
- 'D':向下一个单元格(当前单元格的 $$$y$$$ 坐标减少 $$$1$$$);
- 'U':向上一个单元格(当前单元格的 $$$y$$$ 坐标增加 $$$1$$$)。

你的任务是在场地的一个单元格中放置一个障碍物,以便在执行命令后,机器人将返回到其路径 $$$(0, 0)$$$ 的原始单元格。当然,起始单元格$$$(0, 0)$$$中不能放置障碍物。保证如果没有放置障碍物,则机器人不会返回起始单元。

障碍物通过以下方式影响机器人的运动:如果它试图朝某个方向前进,并且存在障碍物,那么它只是保持在原地(障碍物也仍然存在,也就是说,它不会消失)。

找到任何这样的区域单元格($$$(0, 0)$$$ 除外),如果您在那里放置障碍物,机器人将在执行所有命令后返回到单元格 $$$(0, 0)$$$。如果没有解决办法,请报告。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。

每个测试用例都包含一行,其中包含 $$$s$$$ — 命令序列,仅是大写拉丁字母“L”、“R”、“D”、“U”。 $$$s$$$ 的长度介于 $$$1$$$ 和 $$$5000$$$ 之间(含边界值)。对 $$$s$$$ 的附加约束:如果没有障碍物,执行此命令序列会导致机器人到达 $$$(0, 0)$$$ 以外的某个单元格。

测试中所有 $$$s$$$ 的长度总和不超过 $$$5000$$$。

输出

对于每个测试用例打印一行:

- 如果有解决方案,则打印两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^9 \le x,y \le 10^9$$$),这样 $$$(x, y)$$$ 中的障碍物将迫使机器人返回单元格 $$$(0, 0)$$$;
- 否则,打印两个零(即 0 0)。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

4
L
RUUDL
LLUU
DDDUUUUU

输出 #1

-1 0
1 2
0 0
0 1