SP32091 CSTATE2 - Chessboard State 2: International Chess Tournament

**注意：这是题目 CSTATE1 的较难版本——解决此问题的方法（输入输出格式除外）在那题中依然适用。同时，这也是题目 CSTATE3 的简化版本——解决 CSTATE3 的答案在这里同样能通过。** 在斯洛伐克斯坦，人们决定举办一场全国象棋锦标赛。

输入的第一行包含一个整数，表示**棋盘的数量**。接着是 **t** 组棋盘描述。 每个棋盘的描述开始于两个整数，分别是**棋盘的边长（8）和当前棋盘上的棋子数量**。 然后有 **p** 行描述每个棋子，每行的格式为 '**x y c**'，其中 **1 ≤ x, y ≤ n** 表示棋子的位置；棋盘左上角坐标为 **(1,1)**，右下角坐标为 **(n,n)**。 字符 **c** 表示棋子的类型，取自集合 **{KQRBHPkqrbhp}**，依次代表：国王、皇后、车、象、马和兵。 白方棋子以小写字母表示；棋盘上半部分（即较小的 **y** 坐标）属于白方，白方的兵沿正 **y** 方向移动。 黑方棋子以大写字母表示；棋盘下半部分（即较大的 **y** 坐标）属于黑方，黑方的兵沿负 **y** 方向移动。 每个棋盘描述的结尾后都有一个空行。 尽管棋子数量或位置可能在实际游戏中无法实现，但可以放心的是，每个棋盘上都会有一个白方国王（'**k**'）和一个黑方国王（'**K**'），且不可能有两个棋子位于相同的位置。 输入文件大小是“合理的”——即使包含大量测试用例，每个测试数据的规模也相对较小。具体而言，一个输入文件中的所有 **n + p** 之和不超过 **450,000**。

对于每个棋盘，输出一行结果，可能的结果有： - “**Safe**”：若双方国王均未受到威胁 - “**Impossible**”：若双方国王均受到威胁 - “**{colour}** **Check - m Plausible Moves**”：若某方的国王受到威胁，且存在 **m** 种有效的走法可以解除威胁，其中 **{colour}** 为“**Black**”或“**White**” - “**{colour}** **Checkmate**”：若某方的国王受到威胁，且没有任何走法可以解除威胁，其中 **{colour}** 为“**Black**”或“**White**” #### 附加说明 共有 16 个输入文件，编号为 "0" 到 "15"。文件 0 包含下面给出的例子。文件 1 包含CSTATE1的一半测试数据；文件 2 包含CSTATE1的其余测试数据以及一些大小为100的棋盘。每个文件的时间限制是2.5秒，大约是我在任何输入文件上最慢时间的四倍。不过，如果您认为您的解决方案运行稍微超时，可以联系我，我可能会延长时间限制。 提交后，你可以通过点击结果文本（如“通过”、“答案错误”等）查看每个输入文件的额外信息，例如每个文件的结果以及使用的时间和内存；但没有类似于CSTATE1中的提示信息——如果您在这里遇到难题，可以考虑在CSTATE1中提交以帮助找出您解法中的问题。 **本翻译由 AI 自动生成**