← 返回题目列表

AtCoder · utpc2021_l

L. 迷宫游戏

中文机器翻译题面 查看原题

配点 : 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 每个字符都只出现一次,且不相邻上下左右
  • 所给的迷宫是 可到达状态 从写着 是

入力

输入是按以下格式从标准输入给出的。

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

在第一个用例中,Alice可选择的格子有右上或左下两种,无论选择哪一格,下一步Bob都会选择另一格 . 的格子,从而Bob获胜。

在第二个用例中,Alice将第二行的 . 该值应乘以 # 改变后,Alice获胜。