第三大道

题目描述

有一个用纵向 $H$ 格、横向 $W$ 格的 $2$ 维网格表示的城镇。

从上数第 $i$ 行、从左数第 $j$ 列的格子的信息由字符 $a_{i,j}$ 给出。$a_{i,j}$ 是 S、G、.、#、a ~ z 中的某一个。

# 表示不能进入的格子，a ~ z 表示装有传送装置的格子。

高桥君最初在 S 所在的格子，每秒可以进行以下任一移动：

• 移动到与当前所在格子上下左右相邻的、不是 # 的格子。

• 选择一个与当前所在格子写着相同字符的格子，传送到那里。当当前所在格子是 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。

样例

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

4

将从上数第 $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)$

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

14

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

-1

数据范围

• $1 \le H, W \le 2000$
• $a_{i,j}$ 是 S、G、.、#、英文小写字母中的某一个
• S 所在的格子和 G 所在的格子各恰好有 $1$ 个