006 - 回れ雛月花 -Extra

問題

あっ、雛ちゃんだ可愛いね！！
厄集めを終え、パルスィさんの家に向かう雛ちゃん。
疲れからか、不幸にも黒塗りの機械に追突してしまう。
機械が動き出すと同時に、地震が発生し、
雛ちゃんは遠くに投げ出されてしまった。_{かわいいね}
全ての責任を負う形になった雛ちゃんに対し、
機械の主、河童にとりから言い渡された示談の条件とは・・・

にとり
「この機械はね、この山にスイッチとそれに対応した壁を生み出す装置なの。
いつもあなたは壁に阻まれることがあったかもしれないけど、
どこかにあるスイッチを押すとそれに一つだけ対応した壁が壊れる仕組みになってるわ。
もう一度あの機械を起動すれば直るのだけど。
分かるわね。責任を取って機械を止めてきなさい。
スイッチと対応する壁を示したマップはあげるから、ほら、行ってきなさい。
それまでこの頭のリボンは預かっておくわね。」

雛ちゃんはパルスィさんの家に行く予定だったので早めに終わらせたい。

リボンを返して貰うため、責任を取るため、
雛ちゃんの戦いが始まる！！

入出力形式

入力形式

入力の一行目には、雛ちゃんがいる土地の縦の長さと横の長さ、
スイッチと対応する壁の数 h , w , n が空白区切りで与えられる。
次の行から h行×w列 に渡って、土地のデータ m_i,j が与えられる。

'H' の時雛ちゃんの初期位置である。
'G' の時機械の場所であり目的地である。このマスに到着することをゴールと示す。
'.' の時何もない通過できる箇所である。
'#' の時壁であり通れない箇所である。
'S' の時スイッチであり通過できる箇所である。
'W' の時スイッチと対応した壁であり対応したスイッチを押すと通れるようになる。

その後 n行に渡って、i番目のスイッチの場所 sh , sw　と、
それに対応する壁の場所 wh , ww が空白区切りで与えられる。

h w n
m1,1 m1,2 ... m1,w
m2,1 m2,2 ... m2,w
...
...
mh,1 mh,2 ... mh,w
sh1 sw1 wh1 ww1
sh2 sw2 wh2 ww2
...
...
shn swn whn wwn

出力形式

一マス移動するのに時間を１要するとしたときの、
雛ちゃんが機械を止めるまでにかかる最短時間を出力せよ。
もしも雛ちゃんが機械を止めることが出来なければ、
"Broadcasting accident"を一行に出力せよ。
出力の最後には改行をすること。

制約

• 3 ≦ h,w ≦ 500
• 0 ≦ n ≦ 15

入出力例

入力例一

5 6 2
H.....
###.#.
#S..#W
#W###.
G.#S..
3 2 3 6
5 4 4 2

出力例一

34

この入力例では、
h=3,w=2 のスイッチが h=3,w=6 の壁に対応している。
h=5,w=4 のスイッチが h=4,w=2 の壁に対応している。
そのため、
スタート → スイッチ1 → スイッチ2 → ゴール
へのルートが最短となり、総合の最短時間は 34 である。

入力例二

6 5 1
S..WG
.##..
.#..#
.#...
.###.
H....
1 1 1 4

出力例二

9

後日談

雛ちゃん
「ねぇにとり、どうしてあんな機械を作ったの？」
にとり
「覚えてないの？
ヒナくるんの撮影で使ったじゃないか。」