题目描述

縦 $H$ マス、横 $W$ マスの $2$ 次元グリッドで表された街があります。
上から $i$ 行目、左から $j$ 列目のマスの情報が文字 $a_{i,j}$ により与えられます。 $a_{i,j}$ は S , G , . , # , a ~ z のいずれかです。
# は入ることができないマスを、a ~ z はテレポーターのあるマスを表します。

高橋くんははじめ S のマスにおり、 $1$ 秒ごとに以下のいずれかの移動を行います。

• 現在いるマスと上下左右に隣り合う、# でないマスに移動する。
• 今いるマスと同じ文字が書かれているマスを $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 を出力せよ。

题目大意

给出一张地图，起点 S 终点 G，# 表示墙体。

地图上有若干个传送门，用小写字母表示。

每一秒，您可以移动到相邻位置，或是通过您当前所处的传送门移动到对应的任一传送门。

问您需要的最短时间，若是无法到达输出 -1。

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

4

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$ つ存在する

Sample Explanation 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)$ に移動する