問題
とある迷路があった。その迷路にはA地点とB地点の二つのスタート地点がある。どちらからスタートしても ゴールにたどり着くことは可能であるが、できる限り早くゴールに着きたい。そこで、迷路の情報が与えられるので A地点とB地点のどちらの方がより早くゴールにたどり着くか調べてもらいたい。 そして、それにかかる移動回数も調べてもらいたい。
入力
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。
１行目に迷路の横幅Wと縦幅Hが与えられます。
続くH行に迷路の情報が与えられます。
. ・・・ 通ることが可能なマス
# ・・・ 壁（通ることが不可能なマス）
A ・・・ スタート地点A
B ・・・ スタート地点B
G ・・・ ゴール地点
W H C1,1 C2,1・・・CW,1 C1,2 C2,2・・・CW,2 ・ ・ ・ C1,H C2,H・・・CW,H
出力
より早いスタート地点とそれにかかる移動回数を空白区切りで１行で出力してください。
※ただし、A地点もB地点も同じ移動回数だった場合、Aのほうを出力するようにしてください。
制約
- 1≦W,H≦15
入出力例
入力
3 2 B.. A#G 3 3 ..A .#. B.G 8 8 .#...##. ........ .###..#. ..#..##. ..#...#A B.#....# ##..#... #...##G# 0 0
出力
B 3 A 2 A 14