AT_abc184_e [ABC184E] Third Avenue

[problemUrl]: https://atcoder.jp/contests/abc184/tasks/abc184_e 縦 $ 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` を出力せよ。

### 制約 - $ 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) $ に移動する