002 - Move and Teleport

問題

$H$行$W$列のグリッドがあります。グリッド上から$i$番目、左から$j$番目のマスをマス($i,j$)と表記します。
マス($i,j$)は$C_{i,j}$が「.」のとき空きマスであり、「#」のとき壁を表します。
また、英小文字の場合はテレポーターを表し、同じ文字のテレポーター間を無料で移動できます。
K君は以下のいずれかの行動を繰り返しマス(1,1)からマス($H,W$)まで移動します。
・K君が現在いるマスの1つ左のマスが存在し、そのマスが壁でなければ１つ左のマスに移動する。移動する際、1円払う
・K君が現在いるマスの1つ右のマスが存在し、そのマスが壁でなければ１つ右のマスに移動する。移動する際、1円払う
・K君が現在いるマスの1つ上のマスが存在し、そのマスが壁でなければ１つ上のマスに移動する。移動する際、1円払う
・K君が現在いるマスの1つ下のマスが存在し、そのマスが壁でなければ１つ下のマスに移動する。移動する際、1円払う
・K君が現在いるマスがテレポーターであれば、同じ文字のテレポーターへ移動することができる。移動は無料
K君がマス(1,1)からマス($H,W$)まで移動するのにかかる費用の最小値を求めてください。
移動が不可能な場合-1を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$
$C_1$
$C_2$
 :
$C_H$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq H, W \leq 1000$
• 必ずテレポーターは対応するテレポーターが一つだけある。
• 入力はすべて整数
• $C_{1,1},C_{H,W}$は空きマス

入出力例

入力例1

3 3
.##
.##
...

出力例1

4

入力例2

5 5
..a#.
.##a.
.....
####.
.....

出力例2

6

途中でテレポーターを使うことで目的地に早くつける場合があります。

入力例3

7 5
.#a..
a#.##
.#...
.###.
.....
.####
.....

出力例3

10

テレポーターを素通りしたほうが早い場合があります。