Robot on the Board 2
Contest: Codeforces Round 753 (Div. 3)
Difficulty rating: 2300
Tags: brute force, dfs and similar, graphs, implementation

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).

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
1 1 1
1 1 3
1 1 4
2 1 3
3 1 5
4 3 12
1 1 4

Editorial:
Let's start moving from an arbitrary cell of the table, for example, from $$$(1, 1)$$$. Movement from each cell is specified by the direction given in that cell, so you can run a loop with a stopping condition "exit from the board border or get to the already visited cell". Create a separate array $$$d[r][c]$$$ — how many commands the robot will execute, starting the movement from the cell $$$(r, c)$$$; we will also use it to check whether the cell has already been visited or not (not visited if $$$d[r][c]$$$ is not yet positive).
Finishing the movement from $$$(1, 1)$$$ let's consider two cases.
1. Either we have gone beyond the boundary of the array, then we can say for sure that for the $$$i$$$-th cell from the end of the sequence $$$(r_i, c_i)$$$ the answer is $$$d[r_i][c_i] = i$$$.
2. Or we came to the already visited cell, let it be the $$$t$$$-th from the end in our path. Then at the end of the path, there is a cycle of length $$$t$$$: starting the movement at any cell of this cycle, the robot will walk exactly $$$t$$$ steps until it arrives at the already visited cell. Thus, for $$$i \leqslant t$$$ distance will be equal to $$$d[r_i][c_i] = t$$$, and for all others it will be, as in the first case, $$$d[r_i][c_i] = i$$$.
Let us run the same algorithm from the next cell, which we have not yet considered. There will be three cases of robot stopping the execution of the commands: the first two repeat those already considered above, and the third case is that the robot will come to the cell $$$(r_0, c_0)$$$ already visited on some of the previous iterations of our algorithm. In this case we know that starting from $$$(r_0, c_0)$$$, the robot will make exactly $$$d[r_0][c_0]$$$ steps, so for the $$$i$$$-th cell from the end on the current path $$$d[r_i][c_i] = d[r_0][c_0] + i$$$ will hold.
The first two cases are handled completely in the same way as described above. Each of the cases is eventually reduced to another iteration over the cells visited in the current path. Let's visit all the cells in reverse and mark all values of $$$d$$$.
Such algorithm is enough to repeat until each cell is processed, after which for each cell of the table its $$$d$$$ will be known and we'll only have to choose the maximal value of $$$d[r][c]$$$ among all $$$(r, c)$$$.