Robot on the Board 2

题意翻译

有一个机器人在 $n \times m$ 的棋盘上移动，每个格子中写着 ```L```、```U```、```R```、```D```其中一个字母，依次代表机器人到这个格子后会向左、下、右、上方向走。 机器人不能重复经过一个格子，也不能走出棋盘，问机器人在哪个格子开始走可以走到的格子最多，以及最多能走到多少个格子。 一共 $T$ 组数据。 第一行输入一个数， $T$； 以下 $T$ 组测试数据，每组数据第一行输入 $n, m$ ，然后输入 $n$ 行，每行一个 长度为 $m$ 的只含 L、R、U、D 字符串。 每组测试数据前有一个空行。 对于每组数据，输出一行三个数，前两个数表示机器人起始位置，第三个数表示机器人最多走多少格。若有多个位置符合要求，任意输出一个即可。 保证$1 \le n,m \le 2000$， $1 \le T \le 10000$， $\sum nm \le 4\times 10^6$。

题目描述

The robot is located on a checkered rectangular board of size $ n \times m $ ( $ n $ rows, $ m $ columns). The rows in the board are numbered from $ 1 $ to $ n $ from top to bottom, and the columns — from $ 1 $ to $ m $ from left to right. The robot is able to move from the current cell to one of the four cells adjacent by side. Each cell has one of the symbols 'L', 'R', 'D' or 'U' written on it, indicating the direction in which the robot will move when it gets in that cell — left, right, down or up, respectively. The robot can start its movement in any cell. He then moves to the adjacent square in the direction indicated on the current square in one move. - If the robot moves beyond the edge of the board, it falls and breaks. - If the robot appears in the cell it already visited before, it breaks (it stops and doesn't move anymore). Robot can choose any cell as the starting cell. Its goal is to make the maximum number of steps before it breaks or stops. Determine from which square the robot should start its movement in order to execute as many commands as possible. A command is considered successfully completed if the robot has moved from the square on which that command was written (it does not matter whether to another square or beyond the edge of the board).

输入输出格式

输入格式

The first line contains an integer $ t $ ( $ 1 \le t \le 10000 $ ) — the number of test cases in the test. Each test case's description is preceded by a blank line. Next is a line that contains integers $ n $ and $ m $ ( $ 1 \le n \le 2000 $ ; $ 1 \le m \le 2000 $ ) — the height and width of the board. This line followed by $ n $ lines, the $ i $ -th of which describes the $ i $ -th line of the board. Each of them is exactly $ m $ letters long and consists of symbols 'L', 'R', 'D' and 'U'. It is guaranteed that the sum of sizes of all boards in the input does not exceed $ 4\cdot10^6 $ .

输出格式

For each test case, output three integers $ r $ , $ c $ and $ d $ ( $ 1 \le r \le n $ ; $ 1 \le c \le m $ ; $ d \ge 0 $ ), which denote that the robot should start moving from cell $ (r, c) $ to make the maximum number of moves $ d $ . If there are several answers, output any of them.

输入输出样例

输入样例 #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