1653. [BOI2008]移棋子游戏

【题目描述】

两名玩家，A和B，在一张n*n的方格棋盘上玩游戏。棋盘上的每一格是黑色或者白色。游戏只在白格子上进行——黑色格子被排除在外。两位玩家都有一枚棋子，最初放在该玩家的起点——棋盘上的一个白色格子。两名玩家的起点互不相同。

双方轮流移动。每次移动中，玩家将他的棋子移向一个相邻的白色格子（可以是上下左右）。如果这名玩家把他的棋子移到了对手的棋子所在格，他就可以获得一次额外的移动（从而跳过对手的棋子）。在这种情况下第二次移动的方向可以和第一次不同。

玩家A先移动，然后两名玩家轮流移动。游戏的目标是到达对手的起点。先到达对手起点的玩家获胜，即使这名玩家的最后一次移动跳过了对手的起点。我们希望确定哪名玩家有必胜策略（一名玩家有必胜策略是指无论对手如何移动他都能获胜）。

图1.如果A在头三次移动中向右走，B将在头三次移动中向上走。因此，在第三次移动中B将到达A所在的位置并因此获得一次额外的移动机会。因此B将先到达A的起点并赢得游戏。

图2.A可以先向右走一步再向下走一步。然后，根据B的头两步移动，A将会向下或者向右走并避开B。因此A将会首先到达B的起点，从而赢得游戏。事实上我们证明了 A有必胜策略。

写一个程序：

·读入棋盘的布局和两名玩家的起点。

·找到有必胜策略的玩家。

·输出结果。

【输入格式】

输入文件的第一行有一个整数t，代表数据组数。（1<=t<=10）.

之后描述了t组测试数据。每组测试数据格式如下。

第一行有一个整数n（2<=n<=300），代表棋盘的长度。

接下来的n行描述了棋盘。每行有n个字符（中间没有空格）。每个字符是'.'（白格）,'#'（黑格），'A'（A的起点）或者'B'（B的起点）。

输入保证A，B的起点间存在由白格组成的通路。

另外，对于60%的数据，n<=150，对于40%的数据，n<=40。

【输出格式】

对每组数据输出一行一个字符'A'或者'B'，代表有必胜策略的玩家。

【样例输入】

2
4
A...
.#..
....
...B
4
A...
....
..#.
...B

【样例输出】

B
A

【来源】

BOI2008 Game