Escaping the Maze

Problem Background

Special for beginners, ^_^

Problem Description

When you stand inside a maze, the criss-crossing paths easily make you lose your sense of direction. If you have the map of the maze, things become much simpler.

Suppose you already have the blueprint of an $n \times m$ maze. Find the shortest path from the start to the exit.

Input Format

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 100$): the number of rows and columns of the maze.

Then follow $n$ lines, each a string of length $m$, describing the layout of the whole maze. The characters mean:

• . — open ground
• # — wall
• S — start
• T — exit

Output Format

Print the minimum number of steps from the start to the exit.

Sample Input

3 3
S#T
.#.
...

Sample Output

6

Constraints

$1 \le n, m \le 100$.

Time limit $1$ s, memory $1024$ KiB per test case.

Hint

• Standard BFS over a grid; the first time you expand T is the shortest distance from S.
• Adjacent cells are only the four orthogonal neighbours; walls (#) are not traversable.