Bloxorz Puzzle Solver

This problem is based on the popular game Bloxorz. You are given a rectangular board composed of unit cells. Each cell is one of the following types:

• Rigid: Can support the full weight of the box. (Characters: R, as well as the start cell S and the target cell T which are also treated as rigid.)
• Easily Broken: Can only support half the weight. In other words, a box in the standing position (occupying one cell) cannot be supported if that cell is easily broken (E).
• Empty: Cannot support any weight (denoted by .). The box may not occupy any part of an empty cell.

The box consists of two unit cubes aligned together. It has two possible configurations:

• Standing: Occupies exactly one cell.
• Lying: Occupies two adjacent cells. When the box is lying, it can be either horizontal (occupies cells (x, y) and (x, y+1)) or vertical (occupies cells (x, y) and (x+1, y)).

You can move the box by rolling it 90 degrees around one of its edges. Each move changes the configuration and position of the box as follows:

If the box is standing (state 0):

• Roll Up: becomes vertical, occupying cells $(x-2, y)$ and $(x-1, y)$.
• Roll Down: becomes vertical, occupying cells $(x+1, y)$ and $(x+2, y)$.
• Roll Left: becomes horizontal, occupying cells $(x, y-2)$ and $(x, y-1)$.
• Roll Right: becomes horizontal, occupying cells $(x, y+1)$ and $(x, y+2)$.

If the box is lying horizontally (state 1), with left cell at $(x, y)$ and right cell at $(x, y+1)$:

• Roll Left: becomes standing at $(x, y-1)$.
• Roll Right: becomes standing at $(x, y+2)$.
• Roll Up: becomes horizontal, occupying cells $(x-1, y)$ and $(x-1, y+1)$.
• Roll Down: becomes horizontal, occupying cells $(x+1, y)$ and $(x+1, y+1)$.

If the box is lying vertically (state 2), with top cell at $(x, y)$ and bottom cell at $(x+1, y)$:

• Roll Up: becomes standing at $(x-1, y)$.
• Roll Down: becomes standing at $(x+2, y)$.
• Roll Left: becomes vertical, occupying cells $(x, y-1)$ and $(x+1, y-1)$.
• Roll Right: becomes vertical, occupying cells $(x, y+1)$ and $(x+1, y+1)$.

A move is valid only if every cell that the box occupies after the move is within the grid and is not an empty cell. Moreover, if the box is standing, the cell it occupies must not be easily broken (E); however, when the box is lying the fact that a cell is easily broken is acceptable since each cell only supports half the weight.

Your task is to determine the minimum number of moves required to roll the box from the starting position to the target position. The target is reached only when the box is standing (state 0) exactly on the target cell T. If it is impossible to reach the target, output -1.

inputFormat

The first line contains two integers n and m ($1 \leq n,m \leq 20$), which denote the number of rows and columns of the board.

Then follow n lines, each containing a string of length m made up of characters S, T, R, E, and ., representing the start cell, the target cell, rigid cells, easily broken cells, and empty cells respectively. It is guaranteed that there is exactly one start cell S and one target cell T on the board.

outputFormat

Output a single integer, the minimum number of moves required to reach the target with the box in the standing position. If it is impossible, output -1.

sample

3 3
SRR
TRR
RRR

3