配点 : 300 点
問題文
H 行 W 有一列网格。网格的每个格子中,有放有盘子的格子和没有放盘子的格子。
在放有盘子的格子中,有些格子上放着豆子。每个豆子都是可以区分的,1 一个盘子上可以放置多个豆子。
使用这个网格,爱丽丝和鲍勃打算进行如下游戏。
- 以爱丽丝为先手,轮流进行回合。
- 在自己的回合中,按照后述的“回合中的豆子移动方法”移动一个豆子。如果没有可以移动的豆子,回合的玩家立即失败,非回合的玩家获胜。
当双方都采取最优行动时,请回答谁将获胜。
回合中的豆子移动方法
以下、i 行 j 列的标记 (i,j) 用(1 \leq i \leq H, 1 \leq j \leq W)
表示。首先移动豆子 1 选一个。这颗豆子当前的位置是 (i,j) 时,以下 3 种类型的动作中,满足所有条件的,1 种类型 1 次地执行。
-
3 种类型的动作
- i+1 \leq H 时,(i+1,j) 移动到。
- j=1 时,(i,W) 移动到。否则,(i,j-1) 移动到。
- j=W 时,(i,1) 移动到。否则,(i,j+1) 移动到。
-
条件
- 移动目标格子上有盘子。
- 选中的豆子第一次到达移动目标格子。
制約
- 1 \leq H,W \leq 1000
- H,W 是一个整数。 打印除以
入力
输入是按以下格式从标准输入给出的。
H W
c_{1,1} \cdots c_{1,W}
\vdots
c_{H,1} \cdots c_{H,W}
但是, c_{i,j} 是格子的格子 (i,j) 的状态如下格式表示。
- c_{i,j}=
#时,格子 (i,j) 上没有盘子。 - c_{i,j}=
.时,格子 (i,j) 上有个盘子里面没有豆子。 - c_{i,j}=
B时,格子 (i,j) 上有个盘子里面有一个豆子。
出力
当爱丽丝获胜时Alice当鲍勃获胜时Bob输出为
入力例 1
2 3 B.# #..
出力例 1
Alice
一开始,豆子在 (1,1) 上。
- 爱丽丝的 1 第几回合中,她只能将豆子移动到 (1,2) 上。
- 鲍勃的 1 第几回合中,她只能将豆子移动到 (2,2) 上。
- 爱丽丝的 2 第几回合中,她只能将豆子移动到 (2,3) 上。
- 鲍勃的 2 第几回合中,他不能移动豆子。
因此,这将是鲍勃的失败,也是爱丽丝的胜利。
入力例 2
1 1 B
出力例 2
Bob
入力例 3
1 3 B#.
出力例 3
Alice
豆子 (1,1) 到 (1,3) 可以移动到…请注意。
入力例 4
5 18 #.#..#.#..###..### ##...#.#..#.#..#.. #....#.#..###..#.. ##...#.#..#....#.. #.#..###..#....###
出力例 4
Bob
有时可能不存在豆子。