由 ChatGPT 4o 生成的图像

给你一个包含起点和终点的二维迷宫。你的任务是找到从起点到终点的最快路径。最快路径是指移动步数最少的路径，其中一步是指向左、向右、向上或向下移动一格。当然，你不能穿过墙壁。

然而，有一个限制：如果你在同一个方向上连续移动超过三步，你就会失去平衡并摔倒。因此，禁止在同一个方向上连续移动超过三步。允许向右走三步，然后向左走一步，接着再向右走三步。这与直接向右走五步的效果相同，但步数更多（速度较慢）。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示迷宫的高度和宽度。接下来是迷宫的 ASCII 表示，其中 # 表示墙壁，. 表示空地，S 和 T 分别表示起点和终点。

• $12 \le n \times m \le 200000$。
• $3 \le n, m \le 10000$。
• 字符仅包含 .#ST，且恰好有一个 S 和一个 T。
• 迷宫的外边界全部为 #（墙壁）。

输出格式

输出从起点到达终点所需的最少步数，如果无法到达则输出 -1。

样例

输入样例 1

7 12
############
#S........T#
#.########.#
#..........#
#..........#
#..#..#....#
############

输出样例 1

15

输入样例 2

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

输出样例 2

14

输入样例 3

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

输出样例 3

-1