2022 年上海市大学生程序设计竞赛 - 十月赛

E. Minesweeper Game

单点时限: 1.0 sec

内存限制: 256 MB

Alice and Bob are playing the minesweeper game.

The minesweeper game features a grid board with $n$ rows and $m$ columns. The cell in the top left corner is $(1,1)$, and the cell in the bottom right corner is $(n,m)$. Mines are scattered throughout the board. Fortunately, all cells with mines are already marked on the board before the game (considered as opened cells). Players only need to open the remaining cells, which are all unopened initially.

Alice and Bob play the game in turn (Alice first). Each turn, the player should open an unopened cell. Whenever one cell is opened, and there is no mine in any of its neighbors ($(x,y)$ and $(x’,y’)$ are neighbors if and only if $\max(|x-x’|,|y-y’|)=1$), then all of its unopened neighbors are automatically opened.

A player loses the game if and only if there is no cell to open in his/her turn.

Alice and Bob are clever enough and take the optimum strategy. Therefore, who is the winner?

输入格式

There are multiple test cases.

The first line contains one integer $T$, representing the number of test cases.

For each test case:

The first line contains two integers $n,m$

The following $n$ lines, each line contains a string with length $m$, representing the $n\times m$ minesweeper board. (o for unopened cells, . for mines)

$1\le T\le 10$

$1\le n, m\le 8$

输出格式

One string in a line for each test case, representing the winner’s name.

样例

Input
3
2 2
.o
o.
3 3
.oo
ooo
oo.
4 4
.ooo
oooo
oo.o
oooo
Output
Bob
Alice
Bob

提示

Explanation:

For the first test case:

There are only 2 unopened cells, $(1,2)$ and $(2,1)$. No matter which cell Alice opens in her first turn, the other cell will not be automatically opened. Therefore, Bob can open it to win the game.

For the second test case:

Alice can open the cell $(2, 2)$ first. In the following rounds, whenever Bob opens cell $(x, y)$, Alice can open its central symmetric cell $(4-x, 4-y)$ with respect to $(2, 2)$. (Specially, opening $(1, 3)$ triggers the opening of $(2, 3)$, $(2, 2)$ and $(1, 2)$, while opening $(3, 1)$ triggers the opening of $(2, 1)$, $(2, 2)$ and $(3, 2)$. This is also symmetric.) Therefore, Alice can open the last cell to win the game.