問題
$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
テレポーターを素通りしたほうが早い場合があります。