[THUPC2019]鸭棋

题目描述

#### 题目背景 鸭棋是一种风靡鸭子界的棋类游戏。事实上,它与中国象棋有一些相似之处,但规则不尽相同。在这里,我们将为你介绍鸭棋的规则。 **同时,我们下发了一个模拟鸭棋规则的玩具,你可以结合这个玩具理解题目**(也可以在 AK 后与你的队友进行对弈)。详情请见「玩具使用说明」。 鸭棋在一个 $10\times 9$($10$ 行 $9$ 列)的网格棋盘上进行,网格上的每个格点都可以有棋子停留。对弈双方一方执红(`red`)棋、另一方执蓝(`blue`)棋,双方轮流执行操作,轮到一位玩家操作时,他必须选择一枚自己的棋子,并按照规则进行一步移动。 鸭棋发明者鸭子德规定一局鸭棋由红方执先手,并设计了初始棋盘布局如下: ![initial_board.png](https://cdn.luogu.com.cn/upload/pic/58700.png) ##### 棋子类型与走子规则 棋子分为 $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`。

输入输出样例

输入样例 #1

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

输出样例 #1

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> 查看。