Minimum Steps to Target in a Grid Robot Navigation Problem

You are the manager of a robotic warehouse. The warehouse is represented as a grid of size \(n \times m\) where \(1 \leq n, m \leq 1000\). Each cell of this grid may be:

• Empty (represented by .),
• An obstacle (represented by #),
• The starting position (represented by S), or
• The target position (represented by T).

Your goal is to compute the minimum number of steps required for a robot to travel from the starting position to the target position. The robot can move one cell at a time in one of the four cardinal directions (up, down, left, right), and it cannot move into a cell containing an obstacle. If the target is unreachable, output \(-1\).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two space-separated integers \(n\) and \(m\), where \(n\) is the number of rows and \(m\) is the number of columns in the grid.
2. The next \(n\) lines each contain a string of length \(m\) describing a row of the grid. Each character is one of S, T, ., or #.

outputFormat

Output a single integer to standard output (stdout): the minimum number of steps required to move from the starting position S to the target position T. If the target is unreachable, output \(-1\).

5 5
S..#.
.#.#.
..#..
.#..T
.....

9