給定最大長度的最長路徑

Question

我需要幫助。

我會盡量說明儘可能完美。

假設我有一個2d網格，這是我的「世界」。

網格看起來是這樣的：

的灰色方塊是草。 綠色方塊是道路。 橙色的方塊是沙漠。

中間的藍色方形是我的車。我的車有5格的範圍限制。我想查找並突出顯示所有可以達到的最大範圍或更小的廣場。

駕駛灰色廣場需要1個範圍。沒有什麼花哨。但是，駕駛穿過綠色方形區域會給你+0.5的距離。這意味着，如果你開車的前2個方格是綠色的，你的最大範圍突然變爲6。穿過橙色方形駕駛會給你一個0.5範圍的懲罰。這意味着如果你開車的前2個方格是橙色的，你的最大範圍只有4個。

所以基本上，駕駛到一個方形，花費你1個範圍，但取決於平方，它可以給你額外的範圍或者更小的範圍。

探索考慮獎金的所有路徑。會使我的汽車的最外層看起來像這樣：

所以，我想要一種方法來找到所有標有黑色邊框的方塊，以及其中的所有方塊。這樣我的最大範圍內的所有方塊都會突出顯示。

冗長的問題，但我該如何做到這一點？

我已經研究過寬度和深度第一等，但因爲我可以通過同一個廣場幾條路線我不能標記爲「第一次訪問」，然後永遠不會回到它？

關於此問題的幫助將得到極大的幫助。

感謝您閱讀此處的所有內容。

/E

Answer 1

您可以更容易地代表您的模型，所有的成本，而不是獎金。

1. 你有5天的時間旅行。
2. 開車經過一個廣場的草地需要1天。
3. 駕車經過沙漠的一個廣場需要1.5天。
4. 在道路上行駛需要0.5天的時間。

現在，你有一個簡單的圖表，你可以找到所有不超過5天的距離with Dijkstra's algorithm。