E - 第三大街

得分：500分

问题描述

一个城镇可以用一个二维网格表示，其中有$H$行和$W$列。
$ a_{ij} $ 是描述第 $i$ 行从上到下、第 $j$ 列从左到右的方格的字符。在这里，$ a_{ij} $ 是以下之一： S , G , . , # , a，..., 和 z。
# 代表无法进入的方格，a，..., z 代表具有传送器的方格。

高桥初始位置位于用 S 表示的方格。在每一秒钟，他可以进行以下一种移动：

• 转移到他当前位置的水平或垂直相邻的非#的方格。
• 选择一个方格，其字符与他当前位置的字符相同，并传送到该方格。只有当他处于 a, ..., 或 z 方格时才能使用该移动。

找到高桥从用 S 表示的方格到用 G 表示的方格所需的最短时间。
如果无法到达目的地，则报告 -1。

约束

• $1 \le H, W \le 2000$
• $a_{ij}$ 是 S, G, ., # 或小写英文字母。
• 有且仅有一个用 S 表示的方格和一个用 G 表示的方格。

输入

从标准输入中以以下格式给出：

$H$ $W$

$a_{11}\dots a_{1W}$

$\vdots$

$a_{H1}\dots a_{HW}$

输出

打印高桥从用 S 表示的方格到用 G 表示的方格所需的最短时间。
如果无法从初始位置到达目标位置，则打印 -1。

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

4

记 $(i, j)$ 表示第 $i$ 行从上到下、第 $j$ 列从左到右的方格。
初始时，高桥在 $(1, 1)$。 其中一种在四秒内到达 $(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