CF2041D Drunken Maze

 图片由 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$。

由 ChatGPT 4.1 翻译