单后对单车 Queen vs Rook

## 题目描述 国际象棋特级大师也往往为单后对单车的残局而苦恼。您的任务是写一个程序来计算如果两边都采取最优的走法，残局的结果如何。 如果某一方将获胜，您应该输出获胜一方最少需要几步才能将死对方。然后您需要输出行棋方的所有最优走法。例如，如果行棋方至少在4步 之后才能将死对方，那么您应该输出所有能在4步内将死对方的方案的第一步。 同理，如果行棋方的最优策略也在7步之内被将死，那么您应该输出所有可以在7步之后被将死的走法的第一步，而不应该输出会被更快将死的 走法的第一步。 如果双方都采取最优策略会导致和棋，那么请您输出所有可以和棋的走法的第一步。 ## 输入格式 输入文件的第一行包含一个整数 $ n (0 < n <= 1000) $,它表示测试数据的组数。 接下来$ n $行，每行描述一局残局。每行先描述4个棋子——两个王(K)，一个后(Q),一个车(R)。例如在a4格的白王描述为`WKa4`，在h3格的 黑后描述为`BQh3`，在f7格的白车描述为`WRf7`。棋子的颜色和类型用大写字母表示，格子的编号用`[a-h][1-8]`表示。两个不同的棋子间 有至少1个空格作为分隔符。每行的最后一个字母`W`或`B`表示行棋方。 您可以假设给出的局面是符合国际象棋规则的，也就是说每格最多有1个棋子，非行棋方没有被将军。您还可以假设后和车的颜色总是不同的， 而且有王和车的一方不能进行王车易位。 ## 输出格式 对于每组测试数据，先输出下面三行中的一个 + White mates in `x` + Black mates in `x` + Draw 其中`x`是双方都采取最优策略条件下，某一方取得胜利的最少步数。例如，如果轮到白棋走，但是他已经被将死了，那么应该输出`Black mates in 0`. 在这之后，您应该输出行棋方的所有最优方案的第一步，用简记法表示，需要加上吃子(`x`)，将军(`+`)，将死(`#`)。这些步应该按字典序输出， 参见样例。 如果行棋方被将死，那么输出一个空行。 在每组测试数据之后，输出一个空行。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=15&page=show_problem&problem=1324 [PDF](https://uva.onlinejudge.org/external/103/p10383.pdf) 



6
WKa1 BKa3 WRc2 BQd2 B
BRf5 BKg5 WKb4 WQc5 W
WQb1 BRb3 WKd1 BKd3 B
WKd1 BKf1 BRg1 WQf3 B
WQb6 WKc6 BKf6 BRg6 W
WQb6 WKc6 BKf6 BRg6 B

Black mates in 2
Qd1+ Qe1+
White mates in 27
Qc7
Black mates in 1
Rxb1#
White mates in 0
White mates in 23
Kd5+ Qe3
Draw
Ke5+ Ke7+ Kf5+ Kf7+ Kg5+ Kg7+