由 ChatGPT 4o 生成的图像。
给你一个带有开始和结束位置的二维迷宫。您的任务是找到从起始位置到达结束位置的最快方法。最快的方法是走最少的步数,其中一步是向左、向右、向上或向下移动。当然,你不能穿墙。
然而,有一个问题:如果你朝同一方向迈出三步以上,你就会失去平衡并摔倒。因此,禁止向同一方向连续迈三步以上。可以向右走三步,然后向左走一步,然后再向右走三步。这与向右走五步具有相同的效果,但速度较慢。
输入
第一行包含两个数字 $$$n$$$ 和 $$$m$$$,分别是迷宫的高度和宽度。接下来是迷宫的 ASCII 表示,其中 $$$\tt{\#}$$$ 是墙,$$$\tt{.}$$$ 是空白空间,$$$\tt S$$$ 和 $$$\tt T$$$ 是起始位置和结束位置。
- $$$12 \leq n\times m \leq 200000$$$。
- $$$3\leq n,m \leq 10000$$$。
- 字符只有 $$$\tt{.\#ST}$$$,并且只有一个 $$$\tt{S}$$$ 和一个 $$$\tt{T}$$$。
- 外边界仅为$$$\tt{\#}$$$(墙)。
输出
从起始位置到达结束位置的最小步数,如果不可能,则为 -1。
示例
输入 #1
7 12 ############ #S........T# #.########.# #..........# #..........# #..#..#....# ############
输出 #1
15
输入 #2
5 8 ######## #......# #.####.# #...T#S# ########
输出 #2
14
输入 #3
5 8 ######## #.#S...# #.####.# #...T#.# ########
输出 #3
-1