tkdsheep-solution-0075

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
国际象棋

题目里没有卒，只有王、后、车、马、象
所有棋子的走法和国际象棋的规则是一样的（王车易位不考虑）

另外我出题的时候可能对国际象棋规则了解的不够透彻，在本题中，只要双方的王都还在棋盘上，那么轮到我走的时候我就必须走一步棋，哪怕是把自己王往别人枪口上撞
棋局结束的条件只有一个，就是某一方的王被吃掉

现在给出一个残局，黑棋先走，问黑棋走的第一步有多少种是“good move”的走法（好棋）

好棋的定义：
1.如果这一步直接吃掉对方的王，那么是好棋
2.如果这一步之后，无论第二步对方怎么走，我都可以在第三步吃掉对方的王，那么也是好棋

仔细分析一下好棋的第二个定义，其实比较微妙，并不是简单的“将死”对方
我也有可能走了这一步之后没有构成将军的条件，但对方下一步无论怎么走都会构成“被将军”，那这同样是一步好棋

所以这题最好不要分类讨论，不然很容易漏掉一些情况，最保险、简单直白的做法就是暴搜，枚举每一枚棋子的所有走法

爆搜一共三层，利用博弈的原则，当第二步轮到对方走时，它肯定会选择走一步棋使得我第三步无法吃掉它

本题在算法上考查的是博弈、递归，但本题最大的挑战应该是coding的细节吧，毕竟要模拟5种棋子的走法，数据也比较强（因为要找出所有的好棋），稍微不注意就会写错

我举几个trick的例子：

比如枚举后的走法时，如果某一条路上有对方的棋子，那我可以吃掉它，但不能跳过它，当然也不能跳过自己的棋子，这个很容易被忽略掉
递归搜到第二层对方走的时候，可能会出现对方直接将我的王吃掉的情况，那这时游戏就结束了，不能再搜
棋子移动之后，原来的位置应该变为空格
搜完一种情况之后，要记得回溯

}}}

国际象棋
题目里没有卒，只有王、后、车、马、象
所有棋子的走法和国际象棋的规则是一样的（王车易位不考虑）
另外我出题的时候可能对国际象棋规则了解的不够透彻，在本题中，只要双方的王都还在棋盘上，那么轮到我走的时候我就必须走一步棋，哪怕是把自己王往别人枪口上撞
棋局结束的条件只有一个，就是某一方的王被吃掉
现在给出一个残局，黑棋先走，问黑棋走的第一步有多少种是“good move”的走法（好棋）
好棋的定义：
1.如果这一步直接吃掉对方的王，那么是好棋
2.如果这一步之后，无论第二步对方怎么走，我都可以在第三步吃掉对方的王，那么也是好棋
仔细分析一下好棋的第二个定义，其实比较微妙，并不是简单的“将死”对方
我也有可能走了这一步之后没有构成将军的条件，但对方下一步无论怎么走都会构成“被将军”，那这同样是一步好棋
所以这题最好不要分类讨论，不然很容易漏掉一些情况，最保险、简单直白的做法就是暴搜，枚举每一枚棋子的所有走法
爆搜一共三层，利用博弈的原则，当第二步轮到对方走时，它肯定会选择走一步棋使得我第三步无法吃掉它
本题在算法上考查的是博弈、递归，但本题最大的挑战应该是coding的细节吧，毕竟要模拟5种棋子的走法，数据也比较强（因为要找出所有的好棋），稍微不注意就会写错
我举几个trick的例子：
比如枚举后的走法时，如果某一条路上有对方的棋子，那我可以吃掉它，但不能跳过它，当然也不能跳过自己的棋子，这个很容易被忽略掉
递归搜到第二层对方走的时候，可能会出现对方直接将我的王吃掉的情况，那这时游戏就结束了，不能再搜
棋子移动之后，原来的位置应该变为空格
搜完一种情况之后，要记得回溯