2364 「BalticOI 2008」游戏

题目译自 BalticOI 2008 Day1「Game」

玩家 $\text{A}$ 和玩家 $\text{B}$，在一个 $n\times n$ 的正方形方格板上玩游戏。方格板上的方格要么是白的，要么是黑的。游戏只在白色区域上进行，黑色区域是禁区。初始时，每位玩家的起点上，会放置一个棋子。保证两人起点不同。
玩家交替移动，玩家 $\text{A}$ 先移动。每次移动，玩家会将他的棋子移动到相邻的白色方格中。如果玩家将棋子移动到对方现在的位置，玩家可以再移动一步，以越过对手。注意在这种情况下，第二步移动的方向可以与第一步移动的不同。
这个游戏的目标是玩家的棋子首先到达对方的起点，先到者为胜。即使玩家的最后一步包含两次移动，并且他只是越过了对手的起点（如果对手现在在起点），这个玩家也获得胜利。
给出方格板的布局和两个玩家的起点，判定哪个玩家有必胜策略（如果对手不管怎样移动，一个玩家能获得胜利，就称一个玩家有必胜策略）。

标准输入的第一行包含一个正整数 $t$，表示测试数据的组数（$1\le t \le 10$）。在此之后为 $t$ 组测试数据。每一组测试数据格式如下：
在这组数据的第一行是一个正整数 $n$，表示方格的边长（$2\le n\le 300$），之后的每一行包含 $n$ 个字符（字符之间无空格）。每个字符是 .（一个白色方格），#（一个黑色方格），A（$\text{A}$ 的起点）和 B（$\text{B}$ 的起点）其中之一。

保证在两人的起点间存在一条白色方格的通路。

对于每组数据，输出一行到标准输出，包含一个字符 A 或 B，表示有着必胜策略的玩家。

对于第一组数据：

如果 $\text{A}$ 在前三次移动中移动到方格最右边，$\text{B}$ 将在前三次移动中向上移动。因此，在第三次移动中玩家 $\text{B}$ 将会到达 $\text{A}$ 的方块所在方格，并且给 $\text{B}$ 一次额外的移动机会。因此，$\text{B}$ 会首先到达 $\text{A}$ 的起点并且赢得游戏。

对于第二组数据：

$\text{A}$ 可以先向右移动一次，再向下移动一次。然后，$\text{A}$ 可以由 $\text{B}$ 的前两次移动决定他向下或向右移动来回避 $\text{B}$。这样的话 $\text{A}$ 会首先到达 $\text{B}$ 的起点，因此赢得比赛。事实上我们已经证明了 $\text{A}$ 有必胜策略。

对于 $40\%$ 的数据， $n \le 40$。
对于 $60\%$ 的数据， $n \le 150$。
对于所有数据，$2\le n\le 300$。