D. Drunken Maze
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Image generated by ChatGPT 4o.

You are given a two-dimensional maze with a start and end position. Your task is to find the fastest way to get from the start to the end position. The fastest way is to make the minimum number of steps where one step is going left, right, up, or down. Of course, you cannot walk through walls.

There is, however, a catch: If you make more than three steps in the same direction, you lose balance and fall down. Therefore, it is forbidden to make more than three consecutive steps in the same direction. It is okay to walk three times to the right, then one step to the left, and then again three steps to the right. This has the same effect as taking five steps to the right, but is slower.

Input

The first line contains two numbers $$$n$$$ and $$$m$$$, which are the height and width of the maze. This is followed by an ASCII-representation of the maze where $$$\tt{\#}$$$ is a wall, $$$\tt{.}$$$ is an empty space, and $$$\tt S$$$ and $$$\tt T$$$ are the start and end positions.

  • $$$12 \leq n\times m \leq 200000$$$.
  • $$$3\leq n,m \leq 10000$$$.
  • Characters are only $$$\tt{.\#ST}$$$ and there is exactly one $$$\tt{S}$$$ and one $$$\tt{T}$$$.
  • The outer borders are only $$$\tt{\#}$$$ (walls).
Output

The minimum number of steps to reach the end position from the start position or -1 if that is impossible.

Examples
Input
7 12
############
#S........T#
#.########.#
#..........#
#..........#
#..#..#....#
############
Output
15
Input
5 8
########
#......#
#.####.#
#...T#S#
########
Output
14
Input
5 8
########
#.#S...#
#.####.#
#...T#.#
########
Output
-1