关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道： 订阅。通过购买订阅，您正在帮助确保关于当今塑造我们世界的发现和想法的具有影响力的故事的未来。
网格市是一个小型规划城市，以完全规则的六乘五网格布局，街道南北走向和东西走向。每个街区都有一栋建筑物。
网格市偶尔会遭受大型暴风雪的袭击。“网格市清雪部门”（GridClear）希望居民能够在铺砌的道路上通行，但清雪工作量巨大，他们希望尽量减少犁雪工作，并减少对公众的危险。这意味着路径本身可能会蜿蜒穿过城市，甚至可能会循环，但为了避免碾压众多行人，犁雪机不会在铺砌的道路上折返。
GridClear的负责人向您咨询，以帮助规划路径。您被告知路径必须从网格的外部边界上的某个位置开始，但您可以选择位置，因为网格市有很多车库可供使用。目标是确保对于任何两个南北或东西相邻的街区，居民只需沿着清理过的路径行进几条街道（或穿过几栋建筑物）。路径的“得分”是最坏情况，即到达邻居需要的最多的街道/建筑物数量。穿过已犁的十字路口不花任何代价，但是不可能穿过未犁的十字路口或街道。
您可以假设每个建筑街区的每个角落都有一个入口，并且穿过建筑物到达任何其他角落（甚至是斜对角的角落）所花费的代价与沿着已犁的街道步行一个街区相同。您接受这种简化，因为建筑物内部没有冰。
在热身问题和接下来的问题中，您可能会发现查看由阿雷芬·胡克（Arefin Huq）开发的非常棒的小程序很有帮助，我曾与他一起研究过这个谜题。
http://www.cims.nyu.edu/~ah203/SnowWalkers.html
以下所有屏幕截图均来自该小程序。
热身谜题
假设城市较小，并设置在如下的三乘四城市网格上
http://cs.nyu.edu/cs/faculty/shasha/papers/warmup3x4.tiff
尝试找到一条仅需要犁五条街道的路线，以便行人可以通过最多穿过两条街道从任何街区走到相邻的街区。
热身谜题的答案
回想一下，我们的城市是六乘五，如下图所示
http://cs.nyu.edu/cs/faculty/shasha/papers/oneplow6x5.tiff
仍然是每个街区的每个角落都有一个入口，并且您必须从网格外部开始犁雪。
问题1. 假设您只有一台犁雪机，您是否可以安排一条不超过15条街道的路径，并保证任何街区上的行人都可以在最多步行八个街区的情况下到达任何东西或南北方向的邻居？您的路径看起来像什么？
问题1的答案 问题2. 仍然只有一台犁雪机，您可以设计的最短路径是什么，该路径将保证行人可以通过穿过已清理的十字路口从任何街区走到任何相邻的街区（产生0的成本）？
问题2的答案 问题3. 附近的一个城市刚刚给了您另一台犁雪机。因此，您可以使用两台，但两台都必须从网格外部开始，并且都不能在另一台犁雪机已经犁过的街区上行驶（尽管它们可以在十字路口交叉）。您是否可以找到一种使用两台犁雪机的方法，使得每台犁雪机都犁九条街道，并且行人可以通过穿过已清理的十字路口从任何街区走到任何相邻的街区？
问题3的答案