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 翻译