背景

sx和sb在玩游戏

描述

游戏是这样的,sb有一个大小为R*C的棋盘,但是这个东西曾经被一些人烧坏了,有些格子被烧坏了,然后sb会放一个King上去,他可以走到没有被烧坏的地方,现在我和你两个人轮流来控制他走动,他可以从当前格走到邻近的X(X可以为4或者8,表示是4连通还是8连通)个格子(如果格子没有被烧坏),然后King是不能走过的地方的,否则King会生气的。最后总有不能走的时候,如果某个人无法移动King了,那么那个人就输了。sb先手

输入格式

输入有T组测试数据

第一行两个整数R、C和Ty,Ty=0表示图4连通,Ty=1表示图8连通,R、C意义如题意描述

接下来又R行,每行C个字符,意义如下

'#'表示这个点被烧毁

'.'表示这个点正常

'K'表示这个点事king的初始点

输出格式

共T行,每行一个字符
如果sb有必胜策略,输出A,否则B

样例输入

4

2 2 0

..

K.

4 4 0

....

....

....

K...

4 4 0

####

####

####

K#.#

4 4 0

####

#..#

#..#

K..#

样例输出

A

A

B

B

数据范围与约定

测试点编号1:
T=4, R=4, C=4, Ty=0
测试点编号2~8:
T=100, R=15, C=15, Ty=0
测试点编号9~10:
T=100, R=15, C=15, Ty=1

题目来源

Google Code Jam