本题没有可用的提交语言。

#P1643. 跳棋检查
ID: 644
远端评测题
1000ms
10MiB
Hydro
标签>

描述

跳棋游戏在一个 $8$×$8$ 的红黑相间棋盘上进行，使用交替的方格。两名玩家（红方和白方）各有 $12$ 枚棋子，初始位置如下所示：

移动和捕获规则如下（注：向前移动是指向对手棋盘一侧的移动）：

1. 玩家轮流移动。
2. 一枚棋子可向前斜走一格到任意空方格。
3. 若对手的棋子与当前棋子相邻，且对手棋子后方的方格为空，则当前棋子可向前跳过对手棋子。跳跃后，对手棋子从棋盘移除（被捕获）。若跳跃后，跳跃的棋子还能进行另一次跳跃，则必须继续跳跃。此过程持续到无法再跳跃为止，称为多次跳跃。
4. 玩家若有可能跳跃则必须跳跃。若有多个跳跃可能，玩家可任选其一（甚至可选择单次跳跃而非多次跳跃）。但一旦选择多次跳跃，必须完成整个过程。
5. 对手棋盘一侧的最后一行（棋子无法再向前移动的行）是玩家的升变行。当棋子到达升变行时，会升变为王棋，此后可向前或向后移动和捕获。一旦升变，该棋子的移动结束——升变后不能立即开始跳跃或继续多次跳跃，需等到下一回合。
6. 一枚棋子在一次移动中最多被跳过一次（仅当王棋跳跃时需考虑）。

游戏记录使用上方所示的方格编号。例如，白方的一次简单向前移动可能是 $22$-$18$；红方的单次跳跃可能是 $14$-$23$（捕获白方位于 $18$ 号方格的棋子）；白方王棋的多次跳跃可能是 $22$-$31$-$24$-$15$（捕获红方位于 $26$、$27$ 和 $19$ 号方格的棋子）。

本题中，给定一个游戏进行中的局面和一系列从该局面开始的移动，你需要通过编写一个高级跳棋机器来判断所有移动是否合法。

输入

输入包含多个测试用例。每个用例以两个整数 $r$ 和 $w$ 开头，表示红方和白方的棋子数（$r = w = 0$ 表示输入结束，否则 $1 ≤ r, w ≤ 12$）。接下来一行包含 $r$ 个方格编号，表示红方棋子位置；再下一行包含 $w$ 个方格编号，表示白方棋子位置。正方格值表示普通棋子，负值 $-sq$ 表示 $sq$ 方格上有一枚升变棋子（王棋）。

接下来一行包含一个整数 $m ≥ 1$ 和一个字符（$R$ 或 $W$），分别表示移动次数和当前轮到哪方移动。接下来的 $m$ 行是具体的移动，使用上述符号表示（每个移动中列出的方格数不超过 $13$ 个）。

所有棋盘局面均为合法局面（如无两枚棋子占据同一方格）。保证位于升变行的棋子均已升变——即升变行上不会有未升变的棋子。

输出

对每个测试用例，输出 All moves valid（所有移动合法）或 Move n is invalid（第 $n$ 步移动无效，$n=1$ 对应第一个移动）。若存在多个非法移动，仅输出第一个非法移动。

输入数据 1

4 3  
6 7 8 -16  
9 18 19  
3 W  
9-2  
16-23-14  
2-11-4  
4 3  
6 10 15 19  
18 22 23  
6 R  
19-26  
18-11  
10-14  
22-18  
6-10  
10-15  
0 0  

输出数据 1

All moves valid  
Move 5 is invalid  

来源

2000年北美中东部地区赛