

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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の勝利となります。