004 - 迷路

問題

とある迷路があった。その迷路には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