← 返回题目列表

Codeforces · 2041/D

D. 醉迷宫

中文机器翻译题面 查看原题

由 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