AT_abc184_e [ABC184E] Third Avenue

题目描述

有一个用 $H$ 行 $W$ 列的二维网格表示的城市。
从上到下第 $i$ 行，从左到右第 $j$ 列的格子的内容由字符 $a_{i,j}$ 给出。$a_{i,j}$ 可能是 S、G、.、#、a 到 z 之一。
# 表示不能进入的格子，a 到 z 表示有传送门的格子。

高桥君一开始在 S 格子上，每经过 $1$ 秒可以进行以下任意一种移动：

• 移动到当前格子上下左右相邻的、不是 # 的格子。
• 选择一个与当前格子字符相同的格子并瞬间传送过去。只有当当前格子是 a 到 z 之一时才能使用这种移动。

请你求出高桥君从 S 格子移动到 G 格子所需的最短时间。
如果无论如何都无法到达 G 格子，请输出 $-1$。

输入格式

输入按以下格式从标准输入给出。

$H$ $W$
$a_{1,1}\dots a_{1,W}$
$\vdots$
$a_{H,1}\dots a_{H,W}$

输出格式

输出高桥君从 S 格子移动到 G 格子所需的最短时间。
如果无法从 S 格子到达 G 格子，则输出 $-1$。

输入输出样例 #1

输入 #1

2 5
S.b.b
a.a.G

输出 #1

4

输入输出样例 #2

输入 #2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

输出 #2

14

输入输出样例 #3

输入 #3

11 11
.#.#.e#a...
.b..##..#..
#....#.#..#
.#dd..#..#.
....#...#e.
c#.#a....#.
.....#..#.e
.#....#b.#.
.#...#..#..
......#c#G.
#..S...#...

输出 #3

-1

说明/提示

限制条件

• $1 \leq H, W \leq 2000$
• $a_{i,j}$ 是 S、G、.、#、英文字母小写字母之一
• S 和 G 格子各恰好出现一次

样例解释 1

用 $(i, j)$ 表示从上到下第 $i$ 行、从左到右第 $j$ 列的格子。
一开始高桥君在 $(1, 1)$。例如，可以按如下步骤在 $4$ 秒内移动到 $(2, 5)$：

• 从 $(1, 1)$ 移动到 $(2, 1)$
• 从 $(2, 1)$ 通过传送门瞬间移动到同为 a 的 $(2, 3)$
• 从 $(2, 3)$ 移动到 $(2, 4)$
• 从 $(2, 4)$ 移动到 $(2, 5)$

由 ChatGPT 4.1 翻译