關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您正在幫助確保關於當今塑造我們世界的發現和想法的具有影響力的故事的未來。
網格市是一個小型規劃城市，以完全規則的六乘五網格佈局，街道南北走向和東西走向。每個街區都有一棟建築物。
網格市偶爾會遭受大型暴風雪的襲擊。“網格市清雪部門”（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的答案