← 返回题目列表

AtCoder · kupc2020_h

H. 网格上的豆子

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

配点 : 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

有时可能不存在豆子。