单连岛和线割的理解分享

修改于2024/07/31325 浏览攻略

“单/双连”是我自己发明的简称，意思是两个岛之间有 1/2 条线相连。

若值为 n 且有 m 个直线可到达（下称“相邻”）的岛，则常见的 n=2m-1 时每条边至少单连，n=2m 时每条边必为双连，相信这个大家应该都能摸索出来。

但是有一种其他的情况：比如当前值为 6 且 4 个方向都有相邻岛；然而有一个相邻岛是 1，那么我们可以确定其他三个方向都至少是单连（否则有一个方向不连的话线数量不够）。

因此，我们可以总结一下部分边确定为至多单连时的情况，欢迎大家补充：

m 个相邻岛中有确定的 k 个岛至多单连时，问题退化为：当前岛上值为 n-k 且有 m-k 个相邻岛的情况。“至多单连”有三种可能：

a. 当前岛和目标岛尚未连线，但目标岛上值为 n' 但已经连了 n'-1 条线。（值为 1 看做 n'=1 的特殊情况）

b. 当前岛和目标岛仅连一根线但目标岛已经标记为完成

c. 当前岛和目标岛若双连则会一定产生不连通片（比如两个 2）

在这三种情况下，其他岛至少一根线的要求为 n-k=2(m-k)-1，即 n+k=2m-1 时，类似的其他岛都必须两根线的情况为 n+k=2m。直观感觉是每个点判断周边非明确单连岛的连线数量时，需要加上相邻的至多单连岛的数量。比如一个值为 4 有 3 个邻居的岛，如果附近有 1 个 1，则用 4+1=5，5 和 3 个邻居一定各有一根线。因此两个非 1 方向都是至少一根线。

最后分享一个前期找切入点的办法（即所谓的“线割”）：由于这个游戏里线不能交叉，因此每次连线时都可以查看那些被“割断”的可能性相关的点，即相当于每条垂直于当前连线的可能连线数量都从 0 到 2 变成了 0，或者理解为邻居数量减 1。

#游戏讨论 #攻略