围住一只猫猫需要几步？【多猫预警】( 二 )
文章图片
文章图片
图2 1阶情形恶魔必胜|图源自制而无论天使向哪个方向逃 ， 恶魔都可以隔一格放一个障碍物这样逐渐缩小缺口 ， 保证在天使接触棋盘边缘之前将缺口堵上 ， 因此恶魔是必胜的 。
文章图片
文章图片
一阶的天使问题告诉我们 ， 只要棋盘足够大 ， 让我们可以提前布置好包围圈 ， 就一定能围住天使 。而且天使问题中的棋盘是八连通的 ， 即天使向横竖斜八个方向都可以移动 ， 所以布置一个包围圈至少需要八步 。而围小猫中的棋盘是六连通的 ， 因此包围圈只需要6步 。我们定义猫猫从空白棋盘中心逃脱的最少步数为棋盘的深度n ， 可以看到 ， 围小猫游戏的棋盘深度为5 。
文章图片
文章图片
丰富的游戏经验告诉我 ， n=5显然是不够的 。如果要保证必胜 ， 像天使问题里一样布置一个包围圈至少需要6个障碍物 ， 也就是6步 。因为猫n步就会逃出棋盘 ， 而我们必须在猫逃脱之前花至少一步堵住逃脱的方向 ， 所以棋盘的深度n至少应该为6+1+1=8 。那么棋盘需要有多大才能保证必胜呢？答案就是n=8[3] 。图中偶数号格点为我方放的障碍物 ， 奇数号格点依次为猫猫的行动轨迹 ， 可以看到这种情况下 ， 我方是必定获胜的 。
文章图片
文章图片
图4 n=8时的必胜策略|图源知乎所以 ， 只要棋盘的深度不小于8 ， 即使是一个空白的棋盘 ， 我们也是必定可以围住小猫的 。相应地 ， 在没有障碍物的情况下 ， 棋盘深度小于8时我们是不可能围住小猫的 。终于回到了我们最初的问题：如何在一个n=5的棋盘上利用已有的障碍物围住猫猫 。其实这里的思路还是一样的 ， 那就是：先用若干步布置一个包围圈 ， 然后通过围堵来完善包围圈 。唯一的不同是 ， 由于棋盘不够大 ， 我们必须利用已有的障碍物来布置包围圈 。和棋盘的深度一样 ， 我们定义包围圈的深度为猫猫逃出包围圈的最少步数 。很显然 ， 包围圈越深 ， 留给我们布置防线的步数就越多 。
文章图片
文章图片
先来研究一下包围圈应该是什么样子的：包围圈应当是六边形 ， 与棋盘形状相同 ， 且每条边都经过每个经过格点的圆心 ， 不允许斜着直接连 。只有包围圈的每个顶点（如下面图6中的1-6号点）或者与该顶点相邻且在包围圈上的格点（如下图6中的7-15号点）有障碍物 ， 才能起到挡住猫猫的效果 。如果上述位置没有障碍物的话 ， 就无法保证在猫猫被追赶到此处时闭合包围圈 。
文章图片
文章图片
图5 红色连线没有经过所有经过格点的圆心 ， 是错误的斜连 。上面的深蓝色折线是正确的连法
如果一个顶点或与其相邻且在包围圈上的格点上有障碍物 ， 我们就称这个顶点已完成 ， 定义一个包围圈的完成度为已完成的顶点数量 。下面我们举一个例子来说明 。
推荐阅读
- 年假里，一只被遗忘了的小狗
- 转走学起来 如何拥有一只专属冰墩墩？
- 刘烨晒对比照送新年祝福真老虎变小猫猫
- 生龙活虎闹新春：萌虎帅虎威风虎，你pick哪一只？
- 临近过年，病房里的她收到了一只老虎仔……
- “吃鸡”新年氪金活动来袭！机械兔988一只
- 咋这么可爱！一只狗狗“享受”治疗 另一只冻得直跳jio
- 拜登家庭喜迎一只绿眼虎斑猫！盘点历任美国总统养过的宠物
- MMO怀旧盛宴搞的如何？玩家：百万人抢一只兔子
- 男友养了一只吉娃娃，我忍无可忍提出了分手