003 - パシリーノ・タケノ

あらすじ（ハッピーハロウィーン！）

竹野さんは町内会長にパシラれ・・・頼まれて、町内会に属する全ての家にハロウィーンのお菓子をくばることになった。
町内会に属している家はいくつかのグループに分かれており、それぞれ番号が決められている。この番号をグループ番号と呼ぶ。
一つのグループの内、どこかしらの家にお菓子が届けば同じグループの家全てにお菓子が届くため、同じグループ内でお菓子を届けるのは一つの家でよいということになる。

竹野さんは自宅から出発し、グループ番号が早い順にお菓子を届けた後にそのことを報告するために会長の家に戻ることにした。
最短距離ですべての家にお菓子を届けたいので、データを元に竹野さんが移動する最短距離を求めてほしい。
また、竹野さんは、町内の上下左右の隣接する座標に移動することができ、その移動にかかる時間を1とする。お菓子を渡すのには時間はかからないとする。

入力

入力は、複数のデータセットからなり、入力の終わりはスペースで区切られたゼロ二つからなる行である。 データセットの総数は50以下である。 各データセットは、次の形式をしている。

w h
s(1,1) ... s(1,w)
s(2,1) ... s(2,w)
...
s(h,1) ... s(h,w)

wとhは、それぞれ町の情報を表現する行列データの幅と高さを示す整数であり、それぞれ1 ≤ w, h ≤ 50である。 続くh行はそれぞれ、スペースで区切られたw個の文字から構成されており、文字s(y,x)は、座標(y,x)の地点の状態を示す。

その意味は、以下の通りである。

S：竹野さんの家の地点。必ず1つだけ存在する。
G：町内会長の家の地点。必ず1つだけ存在する。
.：なにもない。
数字：町内会に属している家がある地点。数字はその家のグループ番号を示す。数字は1以上の整数であり、間の数字に抜けはないとしてよい。10以上の数字ももちろんあるため注意すること。

出力

各データセットに対して、Aさんが全てのグループにお菓子を届け、会長の家に辿りつくために必要な最短時間を出力せよ。

制約

入力のところにあります

入出力例

入力例1

7 7
S 5 . . . . 1
2 . 1 . . . 4
. . . . . . .
4 . . . 3 . .
. . . . . . .
. . 3 . . . .
. . . . . 5 G
0 0

出力例1

22

解説

自宅から順に
左から３番目、上から２番目の１
左から１番目、上から２番目の２
左から５番目、上から４番目の３
左から７番目、上から２番目の４
左から６番目、上から７番目の５
の順にお菓子を届けると最短時間の２２で全てのグループにお菓子を届けることが出来る。

入力例2

5 5
S 7 6 5 4
. . . . 3
. . . . 2
. . . . 1
. . . . G
0 0

出力例2

20

解説

一見７から順にとっていけば会長の家まで一直線で行ける気がするが、あくまでグループ番号の小さい順に
お菓子を届けないといけないので、20秒もかかってしまう。

入力例3

8 8
.  2 .  G 2 3 .  .  
.  .  1 .  .  2 1 3 
3 .  .  .  .  1 .  .  
3 .  1 3 .  .  2 .  
1 2 2 .  2 3 3 3 
.  2 .  .  3 .  3 .  
.  3 .  .  .  2 .  2 
1 S .  2 .  2 .  .  
0 0

出力例3

11

入力例4

7 7
S 5 . . . . 1
2 . 1 . . . 4
. . . . . . .
4 . . . 3 . .
. . . . . . .
. . 3 . . . .
. . . . . 5 G
5 5
S 7 6 5 4
. . . . 3
. . . . 2
. . . . 1
. . . . G
8 8
.  2 .  G 2 3 .  .  
.  .  1 .  .  2 1 3 
3 .  .  .  .  1 .  .  
3 .  1 3 .  .  2 .  
1 2 2 .  2 3 3 3 
.  2 .  .  3 .  3 .  
.  3 .  .  .  2 .  2 
1 S .  2 .  2 .  .  
0 0

出力例4

22
20
11