A5407. 走迷宫
编程题
普及/提高-
知识点
题目描述
给定一个二维迷宫，包含起点和终点。你的任务是找到从起点到终点的最快路径。最快路径指的是所需步数最少的路径，每一步可以向左、右、上、下移动一格。当然，你不能穿过墙壁。 不过有一个限制：如果你连续在同一方向上走超过三步，你会失去平衡并摔倒。因此，禁止连续在同一方向上走超过三步。比如，你可以连续向右走三步，然后向左走一步，再连续向右走三步。这和连续向右走五步效果一样，但速度更慢。
输入格式
第一行包含两个整数 $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{\#}$（墙）。
- $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