在电影《巴顿将军》中，将军看到他的两列坦克交叉行驶并陷入堵塞。在沮丧中，巴顿离开了他的吉普车，开始指挥交通。几分钟后，奥马尔·布拉德利将他叫回，去处理更重要的职责。布拉德利嘲讽地称赞巴顿作为交通警察的技能。
但事实是，他是一个糟糕的交通警察。当你不受道路限制时，有更有效的方法让两列队伍互相交叉。
让我们先让问题变得更难一点。假设有四列车辆，每列颜色都不同。如图 1 所示，这些列即将在一个十字路口相遇。
每列车辆都想从矩形区域的对边驶出。因此，绿色车辆想从顶部驶出，橙色车辆想从左侧驶出，依此类推。这样做时，车辆可以并排行驶，而不是单列行驶。
支持科学新闻报道
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您正在帮助确保有关塑造我们今天世界的发现和想法的具有影响力的故事的未来。
因为我们通过允许四列车辆使问题变得更难，所以我们将简化移动规则。 想象一下有一个网格。 每辆车都在一个网格单元位置。 在一列中，相邻的车辆位于相邻的单元格中。 车辆可以在一分钟内移动到其垂直或水平相邻的单元格。 如果两辆车最终进入同一个单元格，它们就会相撞。 您需要避免碰撞。
如图 1 所示，这四列车辆正在汇聚到中心的单个正方形上，因此如果它们同时向中心前进，就会发生碰撞。
问题是如何安排移动，以便所有车辆在尽可能短的时间内穿过其目标侧。 具体来说，假设每种颜色有六辆车，网格尺寸为 13x13。
热身题： 考虑一种情况，其中每列由一辆车组成，如图 2 所示
同样，每辆车都想从对边驶出。 因此，B 想要穿过底边；R 想要穿过右边，依此类推。 我们如何安排才能让所有车辆在四分钟内穿过其目标边？
热身题答案
所有路线都在图 3 中显示
所有车辆都在四分钟后驶出其对边。 很容易看出没有碰撞。
问题： 1. 假设您必须保持车队的顺序，并且它们都必须通过中心。 这需要多长时间？
2. 现在尝试为图 1 中每列六辆车、13x13 网格的问题找到一个 14 分钟的解决方案。
3. 您能证明没有更快的解决方案吗？
4. 假设有八辆车——您可以选择哪些车——可以在旅程的第八分钟以正常速度的两倍（即一分钟两个单元格）行驶。 那么您如何才能在仅十三分钟内解决图 1 中每列六辆车、13x13 网格的问题？
这是一个开放性问题：如果只有四辆车可以在第八分钟加速，您能实现 13 分钟的解决方案吗？ 请记住，不允许碰撞。