[BOI2008]移棋子游戏

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file gam.in Output file gam.out

【题目描述】

两名玩家,A和B,在一张n*n的方格棋盘上玩游戏。棋盘上的每一格是黑色或者白色。游戏只在白格子上进行——黑色格子被排除在外。两位玩家都有一枚棋子,最初放在该玩家的起点——棋盘上的一个白色格子。两名玩家的起点互不相同。

双方轮流移动。每次移动中,玩家将他的棋子移向一个相邻的白色格子(可以是上下左右)。如果这名玩家把他的棋子移到了对手的棋子所在格,他就可以获得一次额外的移动(从而跳过对手的棋子)。在这种情况下第二次移动的方向可以和第一次不同。

玩家A先移动,然后两名玩家轮流移动。游戏的目标是到达对手的起点。先到达对手起点的玩家获胜,即使这名玩家的最后一次移动跳过了对手的起点。我们希望确定哪名玩家有必胜策略(一名玩家有必胜策略是指无论对手如何移动他都能获胜)。

图1.如果A在头三次移动中向右走,B将在头三次移动中向上走。因此,在第三次移动中B将到达A所在的位置并因此获得一次额外的移动机会。因此B将先到达A的起点并赢得游戏。

图2.A可以先向右走一步再向下走一步。然后,根据B的头两步移动,A将会向下或者向右走并避开B。因此A将会首先到达B的起点,从而赢得游戏。事实上我们证明了 A有必胜策略。

写一个程序:

·读入棋盘的布局和两名玩家的起点。

·找到有必胜策略的玩家。

·输出结果。

【输入格式】

输入文件的第一行有一个整数t,代表数据组数。(1<=t<=10).

之后描述了t组测试数据。每组测试数据格式如下。

第一行有一个整数n(2<=n<=300),代表棋盘的长度。

接下来的n行描述了棋盘。每行有n个字符(中间没有空格)。每个字符是'.'(白格),'#'(黑格),'A'(A的起点)或者'B'(B的起点)。

输入保证A,B的起点间存在由白格组成的通路。

另外,对于60%的数据,n<=150,对于40%的数据,n<=40。

【输出格式】

对每组数据输出一行一个字符'A'或者'B',代表有必胜策略的玩家。

【样例输入】

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

【样例输出】

B
A

【来源】

BOI2008 Game