P5380 [THUPC 2019] 鸭棋

#### 题目背景 鸭棋是一种风靡鸭子界的棋类游戏。事实上，它与中国象棋有一些相似之处，但规则不尽相同。在这里，我们将为你介绍鸭棋的规则。 **同时，我们下发了一个模拟鸭棋规则的玩具，你可以结合这个玩具理解题目**（也可以在 AK 后与你的队友进行对弈）。详情请见「玩具使用说明」。 鸭棋在一个 $10\times 9$（$10$ 行 $9$ 列）的网格棋盘上进行，网格上的每个格点都可以有棋子停留。对弈双方一方执红（`red`）棋、另一方执蓝（`blue`）棋，双方轮流执行操作，轮到一位玩家操作时，他必须选择一枚自己的棋子，并按照规则进行一步移动。 鸭棋发明者鸭子德规定一局鸭棋由红方执先手，并设计了初始棋盘布局如下：  ##### 棋子类型与走子规则 棋子分为 $7$ 类，下面介绍了它们的名字以及它们的移动规则。介绍移动规则时，我们默认棋子所处位置为 $\left( x,y\right)$（表示第 $x$ 行的第 $y$ 列，下同），并列出它可以到达的位置： * **王**（`captain`)：可达的位置共 $4$ 个，包括 $\left(x\pm 1,y\right)$ 及 $\left(x,y\pm 1\right)$。 * **士**（`guard`）：可达的位置共 $4$ 个，包括 $\left(x\pm 1,y\pm 1\right)$ 及 $\left(x\pm 1,y\mp 1\right)$。 * **象**（`elephant`）：可达的位置至多 $4$ 个，对于任意 $s_x,s_y\in \left\{ 1,-1\right\}$，分别有： * 如果位置 $\left(x+s_x\times 1 ,y+ s_y\times 1\right)$ 上**无任意一方**的棋子停留，则 $\left( x+s_x \times 2,y+s_y \times 2\right)$ 为一个可达的位置。 * **马**（`horse`）：可达的位置至多 $8$ 个，对于任意 $s_x,s_y\in \left\{ 1,-1\right\}$，分别有： * 如果位置 $\left(x+s_x\times 1 ,y\right)$ 上**无任意一方**的棋子停留，则 $\left( x+s_x \times 2,y+s_y \times 1\right)$ 为一个可达的位置。 * 如果位置 $\left(x ,y+ s_y \times 1 \right)$ 上**无任意一方**的棋子停留，则 $\left( x+s_x \times 1,y+s_y \times 2\right)$ 为一个可达的位置。 * **车**（`car`）：可在**不跨越其他棋子**的前提下，到达同行或同列的所有其他位置。 * **鸭**（`duck`）：可达的位置至多 $8$ 个，对于任意 $s_x,s_y\in \left\{ 1,-1\right\}$，分别有： * 如果位置 $\left(x+s_x\times 2 ,y+s_y \times 1\right),\left(x+s_x\times 1 ,y\right)$ 上均**无任意一方**的棋子停留，则 $\left( x+s_x \times 3,y+s_y \times 2\right)$ 为一个可达的位置。 * 如果位置 $\left(x+s_x \times 1 ,y+ s_y \times 2 \right),\left(x ,y+ s_y \times 1 \right)$ 上均**无任意一方**的棋子停留，则 $\left( x+s_x \times 2,y+s_y \times 3\right)$ 为一个可达的位置。 * **兵**（`soldier`）：可达的位置共 $8$ 个，包括 $\left(x\pm 1,y\right)$ 及 $\left(x,y\pm 1\right)$ 及 $\left(x\pm 1,y\pm 1\right)$ 及 $\left(x\pm 1,y\mp 1\right)$。 **除上面描述的规则之外，棋子移动还有如下额外规则：** * 不能将棋子移动到棋盘外的某个位置。 * 玩家不能将棋子移动到**已经停留了己方棋子**的位置。 * 如果玩家将棋子移动到了一个**已经停留了对方棋子**的位置，那么原本停留在该位置上的这个**对方棋子**将被移出游戏。 ##### 胜利条件与将军局面 玩家在这个游戏中的目标是将对方的**王**移出游戏。一旦一方的**王**被移出游戏，则另一方立即宣告胜利。 对于一个棋盘的状态，如果存在一方有一步合法的操作能够将另一方的**王**移出游戏，则我们说当前局面是一个**将军**的局面。需要友情提示的是，根据定义，将军局面的形成包括（但不限于）如下这些可能： 1. 一方将一枚棋子移动到可以攻击对方**王**的位置 2. 在己方**王**受到威胁时不采取措施躲避 3. 主动将**王**移动至会受到攻击的位置 **除此之外，需要特别说明的是，游戏结束后，由于双方不可再操作，因此不可能出现将军局面，即便此时另一方王处于被「攻击」的位置。** #### 题目描述 今年的 IDCC（International Duck Chess Competition，国际鸭棋大赛）正在如火如荼地进行着。你观摩了一场精彩绝伦的比赛，但你对对弈过程的记忆已经模糊不清了，只有系统留下的他们的**操作序列**，序列中的每个**操作**为当前操作者试图移动某个位置的棋子至另一个位置。你希望用这个序列，来复现出整局棋局的对弈过程。即，对于每步操作，你需要**首先判其是否合法**，若合法，则**进一步求出**： 1. 这步操作移动了哪个棋子。 2. 这步操作后，是否存在棋子被移出游戏，如有则还需求出被移出游戏的棋子。 3. 这步操作后，是否形成将军局面。 4. 这步操作后，游戏是否结束。 可能包含的不合法情况如下： * 此步移动的初始位置无己方棋子停留。 * 此步移动的初始位置有己方棋子停留，但移动不符合规则。 * 游戏已经结束。 序列中的不合法操作是需要被忽略的。比如，如果轮到红方移动，此时序列中的当前操作恰好是不合法的，则这个操作将被忽略，序列中的下一步操作将成为红方这步的操作（如仍不合法则继续忽略，直至出现合法的操作）。

无

无

##### 玩具使用说明 你可以在玩具所在目录下执行如下命令来运行玩具（链接: 提取码: 4d5c）： ``` ./duckchess ``` 特别地，在**初次运行前**，你需要执行如下命令为它添加运行权限： ``` chmod +x duckchess ``` ##### 版权信息 来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。 题解等资源可在 查看。