Steering the Warehouse Drone

A drone flies through a warehouse grid (a list of equal-length strings). It always flies straight ahead, one cell at a time, in one of the four headings up, right, down, left.

• 'S' is the launch cell (exactly one). You choose the drone's first heading for free.
• 'T' is the target (exactly one). The flight succeeds the moment the drone enters T.
• '#' is a shelf: the drone may not enter it, and it may not leave the grid.
• 'R' and 'L' are fixed air vents. Entering one turns the drone's heading 90 degrees clockwise (R) or counter-clockwise (L) at no cost; no command can be given there.
• On an open cell ('.' or 'S'), after entering it you may send one command, turn left or turn right (90 degrees), before it flies on. Each command costs 1.

The route may pass the same cell many times. Return the smallest number of commands needed to reach T, or -1 if that is impossible.

Examples

Input:  grid = ["S..",
                "#.#",
                "..T"]
Output: 2
Explanation: launch right; at (0,1) turn right (now heading down); at (2,1) turn left
             (now heading right) and fly into T.

Input:  grid = ["SR",
                "#T"]
Output: 0
Explanation: launch right; the vent R turns the drone to head down, straight into T.

Input:  grid = ["S#T"]
Output: -1

Constraints

• 1 <= rows, cols <= 80, rows * cols >= 2.

Goals

• Put the heading into the state alongside the cell
• Give free moves weight 0 and turn commands weight 1
• Run 0-1 BFS with a deque instead of a heap