AT_utpc2021_l.Maze Game

有一个纵向 $H$ 行、横向 $W$ 列的网格迷宫。每个格子上写有 S、G、#、. 这四种字符之一。第 $i$ 行第 $j$ 列格子的字符为 $c_{i,j}$。写有 # 的格子为墙，其余格子不是墙。此外，S 和 G 各有且仅有一个，且保证它们不会上下或左右相邻。

当迷宫满足以下条件时，称其为可到达状态：

• 可以从写有 S 的格子出发，仅经过上下左右相邻且不是墙（即不是 #）的格子，到达写有 G 的格子。不能移动到迷宫外。

初始时，保证迷宫处于可到达状态。

Alice 和 Bob 用这个迷宫进行游戏。Alice 先手，双方轮流进行如下操作：

• 选择一个写有 . 的格子，将其变为 #。

若在某位玩家操作结束后，迷宫变为不可到达状态，则该玩家获胜。对于本题给定的迷宫，保证一定会决出胜者。请判断在双方都采取最优策略的情况下，谁会获胜。

有 $T$ 组测试数据，请分别给出每组的答案。

输入按以下格式从标准输入读入。

$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 \le T \le 50$
• $2 \le H,W \le 100$
• 迷宫中的字符仅为 S、G、.、#
• S 和 G 各有且仅有一个，且不会上下或左右相邻
• 给定的迷宫保证处于可到达状态

样例解释 1

在第一个测试用例中，Alice 可选的格子有右上角或左下角两种，但无论选哪个，下一步 Bob 都能选剩下的那个 .，从而 Bob 获胜。第二个测试用例中，Alice 可以将第二行的 . 变为 #，从而 Alice 获胜。

由 ChatGPT 4.1 翻译