0481 - 回れ雛月花 -Advance

時間制限 1 秒 / メモリ制限 64 MB / 得点 9 / Writer root / x 55 / 統計 /

TLE
1sec
MLE
64MB
得点
9

問題

あ、雛ちゃんだ！！

雛ちゃんは、厄集めを終えたぞ！！

この後雛ちゃんは、『魔女っ娘ヒナくるん』の収録が控えている！！

一定の時間が経つまでに天狗のスタジオに行かなければならない！！

あなたは、『魔女っ娘ヒナくるん』の大ファンでもある。

あなたは雛ちゃんのために、スタジオに間に合うかを求めるプログラムを作成することにした。

入力

一行目に、雛ちゃんとスタジオがある土地の地図の縦と横の広さ、 h,w が与えられる。

二行目に、収録開始まであと何分かを示す t が与えられる。

次の行から、土地の地図が与えられる。

"#" は壁であり進めない。

"." は床であり進める。

"H" は雛ちゃんでありスタート地点である。

"S" はスタジオでありゴール地点である。

雛ちゃんは、一マス移動するのに一分を要する。

出力

時間内に間に合うようであれば、スタジオまで最短で何分かかるかを出力せよ。

間に合わないようであれば、"Hina"を出力せよ。

制約

  • 2 <= h,w <= 1000
  • 0 <= t <= h*w

入力形式

h w
t
m0,0 m0,1  ... m0,w-1
m1,0 m1,1  ... m1,w-1
...
...
mh-1,0 mh-1,1  ... mh-1,w-1

入出力例

入力例１

3 4
9
....
#H#.
S...

出力例１

2

スタジオまでの最短時間は２分である。

入力例２

5 6
5
#H.##S
.#....
.#.##.
...#..
.#...#

出力例２

Hina

なお、まにあわんもよう

入力例3

3 3
4
H..
#.#
..S

出力例3

4

入力例4

7 24
89
........................
.#..#..#..#...#.....#...
.#..#.....##..#....#.#..
.####..#..#H#.#...####..
.#S.#..#..#..##..#....#.
.#..#..#..#...#..#....#.
........................

出力例4

14