网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[BOI2008]移棋子游戏
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | gam.in | 输出文件 | 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