Problem Statement
以网格图的形式给你一棵树，Alice 和 Bob 在树上博弈，一开始双方都知道对方的初始位置。
每轮开始时有 Alice 先走，移动到相邻的结点上，然后 Bob 也移动到一个相邻的结点，注意不能在原地不动。
当某个人移动完后如果两人在同一结点 Alice 胜。在很多步内 Alice 无法抓到 Bob 的话，Bob胜。
你需要计算 Alice是否存在一条移动路径，使得在 Bob 知道 Alice 的移动路径的情况下仍然必败。
Alice and Bob are playing a game on a rectangular board.
Rows and columns are both numbered starting from 0.
We will use (i, j) to denote the cell in row i, column j.
The cell (0, 0) is in the top left corner of the board.
Some cells contain walls, others are empty.
The game is played on empty cells only.
The empty cells form a tree.
A more formal specification:
We say that two cells are adjacent when they share an edge.
A path from cell X to cell Y is a sequence of distinct cells such that the first cell in the sequence is cell X, the last cell is Y, and each pair of consecutive cells in the sequence is adjacent.
The test data for this task has the following property: For each pair X, Y of empty cells in the grid, there is exactly one path from X to Y that consists of empty cells only.
The game is played as follows:
Each player has one piece on the board.
Initially, each piece occupies a different cell.
The players take alternating turns, Alice starts.
In each turn, the player moves his/her piece onto one of the adjacent empty cells.
(Note that moving the piece is mandatory, it is not allowed to keep it in its current cell.)
If at any moment the two tokens occupy the same cell, Alice wins.
If Bob is able to make 100,000 moves, Bob wins.
You are given a String[] field that describes the game board.
Character j of element i of field describes the initial content of the cell (i, j).
The character '.' represents an empty cell, '#' represents a wall, 'A' is an empty cell where Alice's piece starts, and 'B' is an empty cell where Bob's piece starts.
Here is the twist:
The game board is completely in the dark.
Alice and Bob each know the initial location of both pieces.
During the game, Alice has no idea how Bob moves his piece.
However, Bob has an extraordinary ability:
Even before the game starts, he can predict the sequence of Alice's moves with perfect reliability.
(Note that this is actually possible: as Alice does not gain any information during the game, she may as well determine her entire strategy in advance.)
He can then use this knowledge when planning his own moves.
Determine whether Alice has a winning strategy. If she does, return "Alice wins" (quotes for clarity). Otherwise, return "Bob wins".
One possible strategy for Alice is as follows:
- Move to (0, 1).
- Move to (0, 2).
- Move to (1, 2).
- Move to (0, 2).
- Move to (0, 3).
With this strategy, Alice can always win regardless of how Bob moves.