007 - 魔女っ娘ヒナくるん -Magic.47

Magic.47 『Princess Parsee』

前回までのあらすじ

やっとの思いで地下迷宮を脱出したヒナくるん達。

しかしそこはニトゥーリが幻影発生装置で作り出した極寒の雪原であった。

あまりの寒さに体力を奪われ、ついに膝をついたヒナくるん。

そこに、パルスィ姫からある告白が・・・

本編

パルスィ姫

「私ね、本当はニトゥーリの手下だったの・・・

あなたがいなくなる前に、本当のことを伝えたくて・・・」

ヒナくるん

「・・・？パルスィ姫、何を言ってるの・・・？」

パルスィ姫

「あなたに近付いて、親密になって、寝込みを襲う・・・。

あなたは仲間に甘いからって、ニトゥーリの策略よ・・・。

あなたとお泊まりしたあの日・・・私はあなたを殺そうとしたわ・・・。

でも・・・できなかった。

あなたの幸せそうな寝顔を見ていると・・・どうしても・・・・

あなたと、もっと、一緒に居たくて・・・

こうして、あなたと一緒に戦いたくて！！

でも・・・もう・・・あなたは・・・！！」

ヒナくるん

「何も言わないで、姫。

正直に伝えてくれて、私とても嬉しいわ。

姫は、とても優しいのね・・・。

ごめんね・・・私・・・もう・・・・・」

パルスィ姫

「嫌よ・・・ヒナくるん・・・・

・・・私が。・・・・私が守る。

私がヒナくるんを守るんだ！！！！」

ヒナくるん

「ひ、め・・・？

なんだろう・・・あったかい・・・

それも、テレパルスィー、ね。

あなたの熱が、暖かい思い出が、私に流れ込んでくる！！

・・・・もう大丈夫！！

あなたの思い出、しっかり伝わったわ！！

さぁ、ここから脱出しましょう！！」

問題

ヒナくるん達は、今幻影で作られた雪原を彷徨っている！

脱出するためには、雪原のどこかにある、

『幻影発生装置』を破壊しなければいけない！！

ヒナくるん達がいる雪原のデータが与えられるので、

ヒナくるん達が『幻影発生装置』に辿り着くまでの最短時間を求めよ！！

なお、ヒナくるん達の座標は、何回か与えられる！！

座標が与えられるごとに、そこからの最短時間を出力せよ！！！

ヒナくるん達の移動可能時間には限りがあり、

もしも最短時間がヒナくるん達の移動可能時間をオーバーしていた場合、

"Broadcasting accident"を出力せよ！！

入力

h w
q
m1,1m1,2...m1,w
m2,1m2,2...m2,w
..
..
..
mh,1mh,2...mh,w

ヒナくるん達が閉じこめられた雪原の縦の長さ h , 横の長さ w が与えられる。

次の行に、ヒナくるん達の移動可能時間 q が与えられる。

次の行から迷路の情報が与えられる。

'#' は雪の山であり、進めない。

'.' は平坦な道であり、進行可能。

'G' は『幻影発生装置』の場所である。

迷路の情報が入力された後、数行に渡ってヒナくるん達の座標 sh , sw が与えられる。

sh = sw = 0 の時、入力は終了とする。

出力

ヒナくるん達の座標が入力される度に、

ヒナくるん達が移動可能時間までに『幻影発生装置』に辿り着ける場合は、最短時間を出力。

間に合わない場合は、"Broadcasting accident"を出力せよ。

制約

• 一マス移動するのには、時間を"1"要する。
• 1 <= h,w <= 1000
• 0 <= q <= h*w

入出力例

入力例壱

5 5
5
#...G
.....
.....
.....
#.##.
1 3
3 3
4 4
5 2
0 0

出力例

2
4
4
Broadcasting accident