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 \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 翻译