逃离丧尸包围的游戏，你能否逃生？ 第1页

图2为图1的后期局部放大图，速度比为4:1，玩家走法由算法控制：始终走向间隙最大的地方。有意思的是，不管玩家初始位置如何，最终似乎总是会变到图2的模式。但遗憾的是，按照这种走法的话，玩家最后总是会被抓住。

为了方便数值计算，我们先考虑一种简单的策略：走直线。假设初始时刻，一只僵尸在原点处，你在 处向正北方向移动。僵尸在t时刻的位置为 . 依据题意

其中 为僵尸的速度.

上两式消去t，得到

注意到这里y', y''是对x的导数。积分一次得到

其中 。按照题意 。假设 ，则僵尸与你的最小距离应该在 时取得，此时如果僵尸刚好抓到你，则 。将上述值带入 化解得：

对于 ，等号右边 ，因此 .

按照上面的计算结果，开局时如果你在 处，然后一路向北不回头。两边的僵尸列队欢送，你被抓到之前可以一直走出大概 的距离，或者说题目第一问中R的下限是 .

更新：实际上可以考虑一个简单点的问题，只保留某个正方形包围圈上的僵尸，如下图所示。如果有足够大的包围圈可以抓住玩家，那么原问题中也可以抓住玩家。

按照上面的计算，显然存在足够大的正方形，使得玩家如果从原点出发沿任何直线走都不可能逃出。你说我可以走曲线呀？令玩家的点为W，两只相邻的僵尸为Z1和Z2，那么

• 线段Z1Z2减小的速度大致正比于 ，这个角我们可以记为
• 如果你走到Z1Z2附近的时间为T，Z1Z2减小的距离大概就是

直线朝着僵尸走，显然T最小。当然这并不直接说明上面的积分就最小，但是至少说明螺旋向外绕圈的方式是很可疑的，因为时间T多了很多，并且这些多出来的时间里 并没有比直线明显减小。具体有没有一种移动方式使得上面的积分比直线更小呢？应该是有的。但是能不能对于任意大的包围圈都能走出去呢，这个要在确定路线后具体算了。

二更：如果只有两只僵尸，它们之间的间距为1，那么不管它们距离你多远，相对位置如何，你始终可以找到合适的路线从它们中间穿过去。

证明：假设两只僵尸和玩家分别为G1, G2, F. 若0时刻 ,那么玩家就可以从它们中间穿过去，因为：

做辅助僵尸G3, 由于所有僵尸的间距随时间非增，因此若玩家沿y轴直线移动，在玩家到达僵尸G3之前，G2会始终落在两个圆交集的眼形区域中。这意味着F到达G3时，G1与G2之间的间距会大于√2-1. 对于1/100的速度比和安全半径，这个间距足够F从G1G2中间穿过了。

若 ，我们可以先稍微绕圈把这个角度变成 ，这不至于损失太多间距. 以下以 的极端例子来说明（假设图中G1(0)=(0,n), G2(0)=(1,n)）：

首先，如上图所示，如果F向左走，那么线段G1G2会逆时针旋转。这样我们可以让F沿着以G1(0)为圆心，n为半径的圆顺时针走。F走出 的距离后， 必然小于 . 由于速度比为100，这时两只僵尸最多走了n/100的距离，离玩家至少有99n/100的距离。根据相似三角形，此时两只僵尸之间的间距至少为0.99. 玩家按照此证明第一段中的策略（调换G1和G2）即可从两只僵尸中间穿过。

抛砖引玉，如有不当欢迎指出和讨论。