← 返回题目

题库练习走迷宫

← 上一题下一题 →

A5407 | $走迷宫$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个二维迷宫，包含起点和终点。你的任务是找到从起点到终点的最快路径。最快路径指的是所需步数最少的路径，每一步可以向左、右、上、下移动一格。当然，你不能穿过墙壁。 不过有一个限制：如果你连续在同一方向上走超过三步，你会失去平衡并摔倒。因此，禁止连续在同一方向上走超过三步。比如，你可以连续向右走三步，然后向左走一步，再连续向右走三步。这和连续向右走五步效果一样，但速度更慢。

输入格式

第一行包含两个整数 $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

输入 #2

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

输出 #2

输入 #3

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

输出 #3

-1

C++ 编辑器

输入

输出