No.3606 Ice Grid Game
問題文最終更新日: 2026-07-31 20:25:24
問題文
縦 $H$ マス $\times$ 横 $W$ マスからなる氷でできたグリッドがあります。はじめグリッドの上から $R$ 番目、左から $C$ 番目のマスに駒が置かれており、それ以外のマスには何も置かれていません。
ただし、グリッドの範囲外のすべてのマスには障害物が置かれているとみなします。
Alice と Bob は、このグリッドを用いてゲームを行います。Alice が先番、 Bob が後番として、以下の一連の操作を交互に行います。
- 手番のプレイヤーが、上下左右の移動方向のうち、移動方向に隣接するマスに何も置かれていないようなものを指定する。
- その後グリッド上の駒を、移動方向に障害物にぶつかるまで、障害物を置きながらその方向に滑らせることを繰り返す。厳密には以下の通りである。
- もし移動方向に隣接するマスに何も置かれていないならば、駒をそのマスに移動させ、直前にいたマスに障害物を置く。そして同じ方向への移動を継続する。
- もし移動方向に隣接するマスに障害物が置かれているならば、駒を今いるマスに留まらせる。そして移動を終了する。
先に移動できる方向がなくなった方のプレイヤーが敗北し、そうでない方のプレイヤーが勝利します。
両者が最善を尽くしたとき、どちらのプレイヤーが勝利するか答えてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- 入力される値はすべて整数
- $1 \leq T \leq 10^4$
- $1 \leq H, W$
- $1 \leq R \leq H$
- $1 \leq C \leq W$
- 全てのテストケースにおける $H \times W$ の総和は $10^6$ 以下
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$H$ $W$ $R$ $C$
出力
各テストケースについての答えを順に改行区切りで出力せよ。
各テストケースについて、両者が最善を尽くしたとき、 Alice が勝利する場合は Alice 、 Bob が勝利する場合は Bob を答えよ。
サンプル
サンプル1
入力
2 2 3 1 3 1 1 1 1
出力
Alice Bob
$1$ 番目のテストケースについて、例えば以下の手順でゲームが進行します。
- はじめ、グリッドは以下のような状態です。ここで、
@は駒のあるマス、.は何も置いてないマス、#は障害物のあるマスです。
..@
...
- Alice が左方向を選びます。
@##
...
- Bob が下方向を選びます。
###
@..
- Alice が右方向を選びます。
###
##@
- 駒はどの方向にも移動できないため、現在手番である Bob が敗北し、 Alice が勝利します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ