003 - パシリーノ・タケノ

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 2 /


TLE
1sec
MLE
64MB
得点
100

あらすじ(ハッピーハロウィーン!)

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

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

解説

自宅から順に
左から3番目、上から2番目の1
左から1番目、上から2番目の2
左から5番目、上から4番目の3
左から7番目、上から2番目の4
左から6番目、上から7番目の5
の順にお菓子を届けると最短時間の22で全てのグループにお菓子を届けることが出来る。

入力例2

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

出力例2

20

解説

一見7から順にとっていけば会長の家まで一直線で行ける気がするが、あくまでグループ番号の小さい順に
お菓子を届けないといけないので、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