005 - crom君のおつかい

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


TLE
1sec
MLE
64MB
得点
50

問題

crom君は母親にお使いを頼まれた。

この世界には、crom君の家と二つの店、家と一つ目の店をつなぐ道、一つ目の店と二つ目の店をつなぐ道しか存在しない。

普通におつかいに行ってもつまらないと思ったcrom君は、家から一つ目の店までの距離、一つ目の店から二つ目の店までの距離、おつかいに行って帰ってくるまでの距離を測ることにした。

但し、移動は上下左右しかできないものとする。

入力

h w
map0,0 ・・・・・・map0,w-1
・
・
・
・
maph-1,0・・・・・maph-1,w-1

一行目に、マップの縦、横の長さh,wが与えられる。

二行目から、縦、横の長さがそれぞれh,wのマップの情報が入力される。

マップの情報は以下の通りに与えられる。

  • 'H' : 家
  • '.' : 道
  • '#' : 障害物。ここには移動できない。
  • 'S' : 店
  • マップの周りは障害物で囲まれているものとする。
  • 店は2つだけ入力され、必ず道と道を結ぶ。
  • 家から一つ目の店、一つ目の店から二つ目の店はそれぞれ一本の道で結ばれている。
  • 道は一つ目の店を通り、二つ目の店で途切れる。
  • 道がどこかでつながるような入力は与えられず、店をつなぐ道と店以外は障害物が入力される。

出力

  • 家から一つ目の店までの距離
  • 一つ目の店から二つ目の店までの距離
  • おつかいに行って帰ってくるまでの距離
  • を、空白区切りで出力する。

制約

  • 4 ≦ h,w ≦ 100

入出力例

入力例1

4 4
####
#SH#
#S##
####

出力例1

1 1 4

入力例2

6 9
#########
######S##
#####..##
####.S###
###H.####
#########

出力例2

3 3 12