#2364. 「BalticOI 2008」游戏

内存限制:8 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

题目译自 BalticOI 2008 Day1「Game

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

输入格式

标准输入的第一行包含一个正整数 ttt,表示测试数据的组数(1≤t≤101\le t \le 101t10)。在此之后为 ttt 组测试数据。每一组测试数据格式如下:
在这组数据的第一行是一个正整数 nnn,表示方格的边长(2≤n≤3002\le n\le 3002n300),之后的每一行包含 nnn 个字符(字符之间无空格)。每个字符是 .(一个白色方格),#(一个黑色方格),AA\text{A}A 的起点)和 BB\text{B}B 的起点)其中之一。

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

输出格式

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

样例

样例输入

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

样例输出

B
A

样例解释

对于第一组数据:

gridgame1.gif

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

对于第二组数据:

gridgame2.gif

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

数据范围与提示

对于 40%40\%40% 的数据, n≤40n \le 40n40
对于 60%60\%60% 的数据, n≤150n \le 150n150
对于所有数据,2≤n≤3002\le n\le 3002n300