单点时限: 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.
3 2 2 .o o. 3 3 .oo ooo oo. 4 4 .ooo oooo oo.o oooo
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.