[Baltic2008]Game

时间限制:10s      空间限制:162MB

题目描述

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


输入格式

第一行输入数据组数.在[1,10]之间下面的数据用于描述每种对局,其开始给出棋盘的大小.在[2,300]


输出格式


样例输入

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

样例输出

B
A

提示

详见曹钦翔论文


题目来源

没有写明来源