SP32092 CSTATE3 - Chessboard State 3: Intergalactic Chess Tournament

**注意：这是 CSTATE1 和 CSTATE2 的进阶版——本问题的解法（除了输入输出格式）同样可以解决那两道题目。** 在斯洛伐克，一群定居者决定组织一场全国象棋锦标赛。

第一行输入一个整数 **1 - 表示棋盘数量。**接下来是 **t** 个棋盘的描述。 每个描述的第一行包含两个整数，表示棋盘的**边长（8）**和**当前棋盘上的棋子数量**。 接下来的 **p** 行中，每行包含三个信息：`x y c`。其中 `1 ≤ x, y ≤ n` 表示棋子的坐标；左上角的坐标是 `(1,1)`，右下角的坐标是 `(n,n)`。 字符`c`表示棋子的类型，取值范围是 `{KQRBHPkqrbhp}`，依次代表国王、皇后、车、象、马和兵。 白棋用小写字母表示，其棋子在棋盘的上方（`y` 坐标较小），因此白兵向正 `y` 方向移动。 黑棋用大写字母表示，其棋子在棋盘的下方（`y` 坐标较大），因此黑兵向负 `y` 方向移动。 每个棋盘描述后都有一个空行。 虽然棋子的数量和位置可能无法在标准国际象棋局面中出现，但可以假设每个棋盘上有且只有一个白国王 (`k`) 和一个黑国王 (`K`)，并且没有两个棋子会占据相同的位置。 输入文件是合理的，也就是说，如果一个文件包含大量的测试用例，那么这些测试用例的规模会相对较小。具体来说，一个输入文件中所有 `p` 的总和不超过 $10^6$。

对于每个棋盘，输出一行结果，格式如下： - 如果双方国王都不受到威胁，输出 `Safe` - 如果双方国王都受到威胁，输出 `Impossible` - 如果某一方国王受到威胁，并且存在 `m` 种合法移动使得国王不再受威胁，输出 `{colour} Check - m Plausible Moves`，其中 `{colour}` 是 `Black` 或 `White` - 如果某一方国王受到威胁，且不存在任何合法移动能使国王解除威胁，输出 `{colour} Checkmate`，其中 `{colour}` 是 `Black` 或 `White` #### 附加说明 共有 16 个输入文件，编号从 `0` 到 `15`。文件 `0` 是下面给出的例子。文件 `1` 到 `7` 包含了 CSTATE2 的测试数据。 提交后，你可以通过点击结果文本（如“接收”、“答案错误”等），查看每个文件的结果以及使用的时间和内存信息，但不会像在 CSTATE1 中那样提供提示信息。如果你遇到了困难，可以考虑在那里提交以获得关于解决方案的提示。 **本翻译由 AI 自动生成**