#2364. 「BalticOI 2008」游戏

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

题目描述

题目译自 BalticOI 2008 Day1「Game

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

输入格式

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

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

输出格式

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

样例

样例输入

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

样例输出

B
A

样例解释

对于第一组数据:

gridgame1.gif

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

对于第二组数据:

gridgame2.gif

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

数据范围与提示

对于 40%40\% 的数据, n40n \le 40
对于 60%60\% 的数据, n150n \le 150
对于所有数据,2n3002\le n\le 300