#1152. 「THUPC 2019」鸭棋 / duckchess NOI/NOI+/CTSC

题目背景

鸭棋是一种风靡鸭子界的棋类游戏。事实上，它与中国象棋有一些相似之处，但规则不尽相同。在这里，我们将为你介绍鸭棋的规则。

同时，我们下发了一个模拟鸭棋规则的玩具，你可以结合这个玩具理解题目（也可以在 AK 后与你的队友进行对弈）。详情请见「玩具使用说明」。

鸭棋在一个 （ 行 列）的网格棋盘上进行，网格上的每个格点都可以有棋子停留。对弈双方一方执红（red）棋、另一方执蓝（blue）棋，双方轮流执行操作，轮到一位玩家操作时，他必须选择一枚自己的棋子，并按照规则进行一步移动。

鸭棋发明者鸭子德规定一局鸭棋由红方执先手，并设计了初始棋盘布局如下：

棋子类型与走子规则

棋子分为 类，下面介绍了它们的名字以及它们的移动规则。介绍移动规则时，我们默认棋子所处位置为 （表示第 行的第 列，下同），并列出它可以到达的位置：

• 王（captain)：可达的位置共 个，包括 及 。
• 士（guard）：可达的位置共 个，包括 及 。
• 象（elephant）：可达的位置至多 个，对于任意 ，分别有：
  • 如果位置 上无任意一方的棋子停留，则 为一个可达的位置。
• 马（horse）：可达的位置至多 个，对于任意 ，分别有：
  • 如果位置 上无任意一方的棋子停留，则 为一个可达的位置。
  • 如果位置 上无任意一方的棋子停留，则 为一个可达的位置。
• 车（car）：可在不跨越其他棋子的前提下，到达同行或同列的所有其他位置。
• 鸭（duck）：可达的位置至多 个，对于任意 ，分别有：
  • 如果位置 上均无任意一方的棋子停留，则 为一个可达的位置。
  • 如果位置 上均无任意一方的棋子停留，则 为一个可达的位置。
• 兵（soldier）：可达的位置共 个，包括 及 及 及 。

除上面描述的规则之外，棋子移动还有如下额外规则：

• 不能将棋子移动到棋盘外的某个位置。
• 玩家不能将棋子移动到已经停留了己方棋子的位置。
• 如果玩家将棋子移动到了一个已经停留了对方棋子的位置，那么原本停留在该位置上的这个对方棋子将被移出游戏。

胜利条件与将军局面

玩家在这个游戏中的目标是将对方的王移出游戏。一旦一方的王被移出游戏，则另一方立即宣告胜利。

对于一个棋盘的状态，如果存在一方有一步合法的操作能够将另一方的王移出游戏，则我们说当前局面是一个将军的局面。需要友情提示的是，根据定义，将军局面的形成包括（但不限于）如下这些可能：

1. 一方将一枚棋子移动到可以攻击对方王的位置

2. 在己方王受到威胁时不采取措施躲避

3. 主动将王移动至会受到攻击的位置

除此之外，需要特别说明的是，游戏结束后，由于双方不可再操作，因此不可能出现将军局面，即便此时另一方王处于被「攻击」的位置。

题目描述

今年的 IDCC（International Duck Chess Competition，国际鸭棋大赛）正在如火如荼地进行着。你观摩了一场精彩绝伦的比赛，但你对对弈过程的记忆已经模糊不清了，只有系统留下的他们的操作序列，序列中的每个操作为当前操作者试图移动某个位置的棋子至另一个位置。你希望用这个序列，来复现出整局棋局的对弈过程。即，对于每步操作，你需要首先判其是否合法，若合法，则进一步求出：

1. 这步操作移动了哪个棋子。
2. 这步操作后，是否存在棋子被移出游戏，如有则还需求出被移出游戏的棋子。
3. 这步操作后，是否形成将军局面。
4. 这步操作后，游戏是否结束。

可能包含的不合法情况如下：

• 此步移动的初始位置无己方棋子停留。
• 此步移动的初始位置有己方棋子停留，但移动不符合规则。
• 游戏已经结束。

序列中的不合法操作是需要被忽略的。比如，如果轮到红方移动，此时序列中的当前操作恰好是不合法的，则这个操作将被忽略，序列中的下一步操作将成为红方这步的操作（如仍不合法则继续忽略，直至出现合法的操作）。

第一行一个非负整数 ，表示操作序列的长度。接下来依次描述每个操作。

接下来 行，每行 个整数 （，），描述一个欲将 处棋子移动到 的操作。在这里，我们规定左下角（即红方车摆放的位置，图见「题目背景」）为 。

保证 。

输出 行，对于每个操作依次输出复现结果。每行输出一个操作的结果：

• 如果该操作为不合法操作，则请输出 Invalid command。
• 如果为合法操作，则依次回答「题目描述」中的问题 ：
  • 被移动的棋子用 [颜色] [类型]（注意中间包含空格）来描述，请使用它们的英文名称（见「题目背景」）。如，红象为 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

玩具使用说明

你可以在玩具所在目录下执行如下命令来运行玩具（见附加文件）：

./duckchess

特别地，在初次运行前，你需要执行如下命令为它添加运行权限：

chmod +x duckchess

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。