配点 : $500$ 点

問題文

縦 $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 を出力してください。

制約

• $1 \le H, W \le 2000$
• $a_{i,j}$ は S , G , . , # , 英小文字のいずれか
• S のマスと 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