[THUPC2019] 鸭棋

#### 题目背景 鸭棋是一种风靡鸭子界的棋类游戏。事实上，它与中国象棋有一些相似之处，但规则不尽相同。在这里，我们将为你介绍鸭棋的规则。 **同时，我们下发了一个模拟鸭棋规则的玩具，你可以结合这个玩具理解题目**（也可以在 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. 这步操作后，游戏是否结束。 可能包含的不合法情况如下： * 此步移动的初始位置无己方棋子停留。 * 此步移动的初始位置有己方棋子停留，但移动不符合规则。 * 游戏已经结束。 序列中的不合法操作是需要被忽略的。比如，如果轮到红方移动，此时序列中的当前操作恰好是不合法的，则这个操作将被忽略，序列中的下一步操作将成为红方这步的操作（如仍不合法则继续忽略，直至出现合法的操作）。

第一行一个非负整数 $Q$，表示操作序列的长度。接下来依次描述每个操作。 接下来 $Q$ 行，每行 $4$ 个整数 $x_s, y_s, x_t, y_t$（$0\leq x_s,x_t < 10$，$0\leq y_s,y_t < 9$），描述一个欲将 $\left(x_s,y_s\right)$ 处棋子移动到 $\left(x_t,y_t\right)$ 的操作。在这里，我们规定左下角（即红方**车**摆放的位置，图见「题目背景」）为 $\left(0,0\right)$。 保证 $Q\leq 1000$。

输出 $Q$ 行，对于每个操作依次输出复现结果。每行输出一个操作的结果： * 如果该操作为不合法操作，则请输出 `Invalid command`。 * 如果为合法操作，则依次回答「题目描述」中的问题 $1\sim 4$： * 被移动的棋子用 `[颜色] [类型]`（注意中间包含空格）来描述，请使用它们的英文名称（见「题目背景」）。如，红象为 `red elephant`，蓝王为 `blue captain`。 * 被移出游戏的棋子的描述方式与上面类似。特别地，**如果无棋子被移出游戏，则该问题的答案为 `NA`**。 * 用 `yes`、`no` 分别表示形成、不形成将军局面。 * 用 `yes`、`no` 分别表示游戏结束、游戏不结束。 * 用 `;`（分号）将所有问题的答案隔开。 * 比如，四个问题的答案分别为：被移动的棋子是蓝车，无棋子被移出游戏，形成将军局面，游戏未结束。则该行应输出 `blue car;NA;yes;no`。

18
0 0 7 0
9 0 8 0
0 1 1 3
0 2 2 0
0 3 1 2
0 4 0 3
9 4 8 4
3 2 2 3
7 0 4 2
7 0 5 3
9 2 7 4
2 0 4 3
9 1 8 3
4 3 6 6
7 4 9 2
8 4 9 4
6 6 9 4
9 8 8 8

Invalid command
Invalid command
Invalid command
Invalid command
red guard;NA;no;no
Invalid command
blue captain;NA;no;no
red soldier;NA;no;no
Invalid command
Invalid command
blue elephant;NA;no;no
red duck;NA;no;no
blue horse;NA;no;no
red duck;blue soldier;no;no
Invalid command
blue captain;NA;yes;no
red duck;blue captain;no;yes
Invalid command

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