题目描述

一个 $n \times n$ 的棋盘，每个格子要么是黑色要么是白色。白格子是游戏区域，黑格子表示障碍。指定两个格子 $\text{A,B}$，分别是先手方和后手方的起始格子。 $\text{A}$ 和 $\text{B}$ 这两格子不重合。游戏中，双方轮流操作。每次操作，玩家向上下左右四个格子之一走一步，但不能走进黑色格子。有一种特殊情况，当一方玩家，恰好走到当前对方所在的格子里，他就可以再走一步（不必是同一方向），“跳过对手”。胜负的判定是这样的，若有一方走进对方的起始格子，就算获胜，即使是跳过对方，也算获胜。输入一个棋盘和双方开始位置，判定胜负归属。

输入格式

第一行输入数据组数 $T$。

下面的数据用于描述每种对局，其开始给出棋盘的大小 $n$。

接下来 $n$ 行每行 $n$ 个字符表示对局的初始状态，其中 . 表示白格子，# 表示黑格子，A、B 表示先后手的起始位置。

输出格式

如果先手获胜，则输出 A，后手获胜，则输出 B。

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

B
A

数据规模与约定

对于 $100\%$ 的数据，$1 \le T \le 10, 2 \le n \le 300$。

题目来源

详见曹钦翔论文。