← 返回题目列表

Codeforces · 1607/F

F. 棋盘上的机器人 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$$$ 行,其中第 $$$i$$$ 描述了电路板的第 $$$i$$$ 行。它们中的每一个都恰好有 $$$m$$$ 个字母长,并由符号“L”、“R”、“D”和“U”组成。

保证输入中所有板的尺寸总和不超过$$$4\cdot10^6$$$。

输出

对于每个测试用例,输出三个整数 $$$r$$$、$$$c$$$ 和 $$$d$$$ ($$$1 \le r \le n$$$; $$$1 \le c \le m$$$; $$$d \ge 0$$$),这表示机器人应该从单元格 $$$(r, c)$$$ 开始移动,以完成最大移动次数$$$d$$$。如果有多个答案,则输出其中一个。

示例

输入 #1

7

1 1
R

1 3
RRL

2 2
DL
RU

2 2
UD
RU

3 2
DL
UL
RU

4 4
RRRD
RUUD
URUD
ULLR

4 4
DDLU
RDDU
UUUU
RDLD

输出 #1

1 1 1
1 1 3
1 1 4
2 1 3
3 1 5
4 3 12
1 1 4