自动搬运

查看原文

来自洛谷，原作者为

	olegekei 这下真的AFO了。

搬运于2025-08-24 21:46:19，当前版本为作者最后更新于2023-02-11 09:49:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注意：

本题解提供的是码量极大，细节巨多，分类讨论多种情况的思路！

---

见到题目要求输出的是最小步数，我们很容易想到从 $1$ 步开始向多步枚举的思路，本题解也是参照这种思路来写的，下面开始分类讨论：

一步到位（无需任何花里胡哨的操作）

这种情况不难判断，只需要找到四个连在一起的黑子还有没有空位能够连成 $5$ 个即可，比较无脑。但是注意容易出现 1 1 0 1 1 的情况，也就是空位可能在中间，不要忽略掉这种情况。

---

下面要开始结合图片进行说明了（大量分讨）。

定义几个说法：

• 活的：意为棋子中间为连珠，且两头都没有被另一方棋子堵住（黑子例子形如 0 0 1 1 1 0 0）。
• 半死：意为棋子中间为连珠，但是两头中有一头被挡住（黑子例子形如 2 1 1 1 0 0）。
• 死的：两头全部被堵住，黑子例子形如 2 1 1 1 1 2（2 1 1 1 0 2 也算作死的）。

两步到位

需要考虑两种情况：

• 一种情况为黑子有活的三连珠（当然形如 0 1 0 1 1 0 也可以，不一定三颗珠子都要连在一起），此时绿色点位 $(3,2)$ 与 $(3,6)$ 是期望的下一步。

• 一种情况为黑子有两个半死的三连珠连在一起（不好描述，见下图）。

此时期望下在绿色点位 $(3,2)$，白色只能堵 $(3,1)$ 和 $(6,2)$ 的其中一个，我们只需要下在另一个点位即可获胜。

三步到位（开始烧脑）

从三步开始，情况就变得复杂了起来。

• 情况 1：落子之后形成两个活的三连珠（如下图，期望落子 $(3,3)$，三步原因显然）。

• 情况 2：落子之后形成一个半死的四连珠和一个活的三连珠（如下图，期望落子 $(3,3)$，白子必堵在 $(6,3)$，接下来两步连上剩下那个活的三连珠即可）。

上面两种情况简称“两个活三”和“一个活三一个半死的四”，因为下面仍会用到这两种情况。

四步到位

从四步开始，就需要涉及到一个连接的思想。可以参考情况 1 与情况 2。

• 情况 1：$2+1+2$ 形，前两步下在两个绿圈上即可形成两个活三（会被白子堵住一个）。情况很难处理，需要考虑到中间的黑子可以和上下的两连珠接在一起，两步形成三个三连珠。

• 情况 2：$1+2+2$ 形，原理同上，不再过多解释，第一步可以任意下在六个绿圈其中之一。

定义由四步转到三步的情况为“胜负一手”，下文会提到。

$k$ 步到位

前面四步都是可以判断出来的，但是五步之上就需要上一个台阶了。你需要让你的程序学会下五子棋，考虑如何同时造出两个活的三连珠。因为题目说明了没有禁手，五步之后你是真正在玩一个五子棋的残局。如下样例（没标绿圈，答案在下一行公布，可以思考一下程序如何实现）：

第一步下在 $(4,6)$ 即可获胜。

第一步造出 $\{(4,6),(5,5),(6,4)\}$ 的活三，第二步胜负一手下在 $(3,5)$ 造出 $\{(3,5),(4,6),(5,7)\}$ 的活三，第三步即可下在 $(4,5)$ 关键位置，造出横竖两个活三，再加两步结束游戏，共需 $5$ 步。

本人的思路是让程序尝试每一步都造出活三或半死的四，造出后继续搜索下一步是否能同时造出两个活三（或一个活三，一个半死的四），如果不能就去搜索下一个活三或半死的四。

但是，你需要考虑白子获胜的可能

如下样例：

四步之后会变成下图：

如果你下一步尝试去连第 $4$ 行的活三，白子会直接下在 $(2,5)$，黑子就会输掉。所以你需要下在 $(2,5)$（此时 $(2,5)$ 也恰好是胜负一手），白子必堵第四行的活三 $(4,3)$ 或 $(4,7)$，你只需要下在另一边即可获得一个半死的四和一个活三，最佳步数为 $8$ 步。

另外即便是可以四步之内到位，仍需考虑一下白子获胜的可能性，如下图：

第一步下在 $(5,1)$，最佳步数为 $3$ 步。

总结一下

四步之内的情况可以判断出来，四步之外可能需要写一个近似的人工智能去下五子棋，同时每一步还需要考虑白子获胜的可能性，去削减掉这种可能（也就是说对于白子可能也需要写一个近似于黑子的人工智能）。

幸运的是题目没有提到无解的情况，也就是说给出的残局黑子一定能够获胜，省去了很多（？）无解的分类讨论。