004 - 魔女っ娘ヒナくるん -Magic.46

Magic.46 『Prisoned and Connected』

前回までのあらすじ

ついに敵アジトに侵入したヒナくるんとパルスィ姫！！

しかし敵の参謀、ニトゥーリによって二人ははぐれ、地下迷宮に閉じこめられてしまった！！

パルスィ姫の能力、「テレパルスィー」によって互いの位置を把握したヒナくるん達！！

はたして二人は、この迷宮から脱出することが出来るのか！？

本編

パルスィ姫

「ヒナくるん！！聞こえる！？」

ヒナくるん

「聞こえるわ！！パルスィ姫ね？」

パルスィ姫

「そうよ！！よく聞いて！！

今あなたの下に、緑色のパネルがあるでしょ？

私のところにも、同じパネルがあるの！！

どうやらこの迷路、私があなたのところのパネルを、

あなたが私のところのパネルを踏むことで脱出できるらしいわ！！」

ヒナくるん

「本当！？じゃあ早速移動しましょう！！」

パルスィ姫

「待って！もうひとつ大切なことがあるの！！

ずっとひとつのマスに留まってると、敵に察知されて襲われるわ！！

だから、もしも私のマスに着いても、一度隣のマスに移動したりして、動き続けるのよ！？」

ヒナくるん

「分かったわ！！でもどうして姫はそのことを・・・？」

パルスィ姫

「・・・その話は後！！まずは脱出しましょう！！」

問題要旨

ヒナくるん達が閉じこめられた迷路の縦の長さ h , 横の長さ w が一行目に与えられる。

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

ヒナくるん達が迷路から脱出できれば脱出できるまでの最短時間を、

出来なければ"Broadcasting accident"を出力せよ。

'#' は壁であり、進めない。

'.' は床であり、進行可能。

'H' はヒナくるんの初期位置であり、パルスィ姫のゴールである。

'P' はパルスィ姫の初期位置であり、ヒナくるんのゴールである。

迷路から脱出する条件は、ヒナくるんとパルスィ姫が同時に各ゴールに辿り着いたときである。

制約

• ヒナくるんとパルスィ姫は、上下左右にしか移動できない。
• 一マス移動する際には、時間を'1'要する。
• 同じマスに時間'1'以上滞在することはできない。 つまり、常に二人は移動する必要がある。
• ヒナくるんとパルスィ姫は、すれ違うことは出来ない。 勿論同じマスに滞在することも出来ない。
• 1 <= h,w <= 30
• 2 <= h*w <= 900

入出力例

Input example 1

5 5
#####
#H..#
#.#.#
#..P#
#####

Output example 1

4

Input example 2

5 5
#####
#H.P#
#.#.#
#...#
#####

Output example 2

6

Input example 3

2 3
.HP
#..

Output example 3

3

Input example 4

3 5
#####
#H.P#
#####

Output example 4

Broadcasting accident

ヒナくるんとパルスィ姫がすれ違うことは不可能である。