L - Maze Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

縦 H 行、横 W 列のグリッド状の迷路があります。 各マスには S , G , # , . のいずれかの文字が書かれています。i 行目 j 列目のマスに書かれている文字は c_{i,j} です。# と書かれたマスは壁になっており、そうでないマスは壁ではありません。 また、S と G は 1 つずつで、上下左右に隣接していないことが保証されます。

迷路が次の条件を満たす時、到達可能な状態 と呼ぶことにします。

  • S と書かれたマスから、G と書かれたマスに、上下左右に隣接する壁でないマス (つまり # と書かれてないマス) のみを通って到達できる。

    ただし、迷路の外に出るような移動はできない。

最初、迷路は 到達可能な状態 であることが保証されます。

Alice と Bob がこの迷路を使ってゲームをします。 Alice が先手で、交互に以下の操作を行います。

  • . と書かれたマスを 1 つ選び、 # と書かれたマスに変更する。

先に自分の操作終了時に、迷路が 到達可能な状態 でなくなったプレイヤーの勝利となります。 本問題の制約下で与えられる迷路では、必ず勝者が決定することが証明できます。 二人が最適に行動した場合、どちらが勝つか求めてください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \le T \le 50
  • 2 \le H,W \le 100
  • 迷路に含まれる文字は、S, G, ., # のいずれか
  • S と G は 1 つずつ含まれ、上下左右に隣接していない
  • 与えられる迷路は 到達可能な状態 である

入力

入力は以下の形式で標準入力から与えられる。

T 
\mathrm{case}_1
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

H W
c_{1,1}c_{1,2}\ldots c_{1,W}
c_{2,1}c_{2,2}\ldots c_{2,W}
\vdots
c_{H,1}c_{H,2}\ldots c_{H,W}

出力

各テストケースについて、Aliceが勝つ場合は Alice、Bobが勝つ場合は Bob と出力せよ。

入力例 1

2
2 2
S.
.G
2 3
#G#
S.#

出力例 1

Bob
Alice

1つめのケースでは、Aliceが選べるマスは右上か左下の2通りですが、どちらを選んでも次にBobがもう一方の . であるマスを選択してBobが勝ちます。

2つめのケースでは、Aliceが2行目の . を # に変えてAliceの勝利となります。