H - Beans on the Grid Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

H 行 W 列のグリッドがあります。グリッドの各マスには、皿が置かれているマスと皿が置かれていないマスがあります。

皿が置かれているマスのうち、いくつかのマスに豆が置いてあります。それぞれの豆は区別でき、1 つの皿には複数の豆を乗せることができます。

このグリッドを使って、AliceとBobは次のようなゲームをしようと考えています。

  • Aliceを先手として、手番を交互に繰り返す。
  • 自分の手番では、後述する「手番における豆の動かし方」に沿って豆を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) には豆が1つ入っている皿がある。

出力

Aliceが勝利するときはAliceと、Bobが勝利するときはBobと出力せよ。

入力例 1

2 3
B.#
#..

出力例 1

Alice

はじめ、豆は (1,1) にあります。

  • Aliceの 1 回目の手番では、豆を (1,2) に移動させるしかありません。
  • Bobの 1 回目の手番では、豆を (2,2) に移動させるしかありません。
  • Aliceの 2 回目の手番では、豆を (2,3) に移動させるしかありません。
  • Bobの 2 回目の手番では、豆を動かすことができません。

したがって、Bobの敗北となり、Aliceの勝利となります。

入力例 2

1 1
B

出力例 2

Bob

入力例 3

1 3
B#.

出力例 3

Alice

豆を (1,1) から (1,3) へ動かせることに注意してください。

入力例 4

5 18
#.#..#.#..###..###
##...#.#..#.#..#..
#....#.#..###..#..
##...#.#..#....#..
#.#..###..#....###

出力例 4

Bob

豆が存在しないこともあります。