問題
−人類をホモに変えてしまう感染症のパンデミックが発生する中、浜松工業高等学校情報処理部の亮裕（あき）、拓実（たくみ）、友貴（きーさん）、啓太（けーくん）の４人は文化祭の準備のため社畜していた。−
あき 「最近学校が好きだ（意味深）」
たくみ 「バカ言ってないで、さっさと準備手伝えよ」
あき 「はぁ〜い♪（適当）」
けーくん 「ゆうき先輩、これどうします？」
きーさん 「そうねぇ、そこに置いてくれるかしら？」
けーくん 「わかりました」
あき 「文化祭、楽しみだね〜（現実逃避）」
けーくん 「そうですね。当日楽しむためにもしっかり準備しないとダメですよ？」
あき 「わかってるって（大嘘）」
きーさん 「でも、今日は終わりにしましょうか。明日また準備しましょう？」
たくみ 「よしっ、じゃあ片付けるか！」
あき 「……う〜ん、その前にちょっとトイレ……（手遅れ）」
たくみ （トイレか……一番近いトイレに行くにも、ヤツらがいるかもしれないな……）
たくみ 「私もついて行くよ。いいだろ？きーさん？」
きーさん 「ええ、もちろんよ。たくみがついて行ってくれたら安心だわ」
あき 「早くしないと漏れちゃうよぉ〜（手遅れ２回目）」
たくみ （ヤツらにできるだけ会わない最短の経路を通ってトイレに行こう）
けーくん 「二人とも、気をつけて行って下さいね」
あき・たくみ「いってきま〜す（笑）」
課題
まず、H×Wのフロアの地図が与えられる。フロアの状態は以下の通りである。
- 'S' : 部室
- 'G' : トイレ
- '.' : 通路
- '#' : 壁
- 'H' : ホモ
フロア内は１秒単位で隣接する上下左右のマスに移動することができ、あきとたくみは常に同じマスにいると考えて良い。
次に、たくみがホモを倒せる回数Nが与えられる。これはホモがいるマスに移動できる回数と考えて良い。
これを超えてホモがいるマスに移動した場合、二人はホモになってしまう。
以上のデータが与えられたとき、部室からトイレまでのホモにならない最短経路を出力せよ。
もしそのような経路がない場合は"DAISUKI"と出力する。
入力
H W c1,1c1,2...c1,W c2,1c2,2...c2,W ... ... cH,1cH,2...cH,W N
出力
部室からトイレまでのホモにならない最短経路、または、"DAISUKI"を出力する。
制約
すべての入出力ケースについて以下を満たす。
- 1 ≦ H ≦ 50
- 1 ≦ W ≦ 50
- 0 ≦ N ≦ 10
入出力例
入力例1
5 5 #.HHH #.HS. .##H. #HHH. #G.HH 2
出力例1
7
入力例2
3 3 #S# HHH HGH 0
出力例1
DAISUKI