algorithm - 给定最大长度的最长路径

Question

我需要帮助。

我会尽量解释清楚。

假设我有一个二维网格，它是我的“世界”。

网格看起来像这样:

灰色方 block 是草。绿色方 block 是道路。橙色方 block 是沙漠。

中间的蓝色方 block 是我的车。我的车有 5 个方格的范围限制。我想找到并突出显示我可以在最大范围或更小范围内到达的所有方 block 。

驾车穿过灰色方 block 需要 1 个距离。没有什么花哨。然而，驾车穿过绿色方 block 可为您提供 +0.5 范围。这意味着，如果您开车经过的前 2 个方 block 是绿色的，那么您的最大射程突然变成了 6。驾车穿过橙色方 block 会给您 -0,5 范围惩罚。这意味着如果您开车经过的前 2 个方 block 是橙色的，则您的最大射程仅为 4。

所以基本上，开车到一个广场需要 1 个范围，但根据广场的不同，它可以给你额外的范围或更小的范围。

在考虑奖金的情况下侦察所有路径。将使我的汽车的最远距离看起来像这样:

是的，我想要一种方法来找到所有标有黑色边框的方 block ，以及它们内部的所有方 block 。这样我的最大范围内的所有方 block 都会突出显示。

这个问题很长，但是我该如何实现呢？

我首先研究了广度和深度等等，但由于我可以通过同一个广场走几条路线，所以我不能第一次将其标记为“已访问”，然后再也不会返回它？

在此方面的帮助将不胜感激。

感谢您一路阅读到这里。

/E

Answer 1

您可以更轻松地展示您的模型，所有这些都是根据成本而不是奖金。

1. 您有 5 天的时间旅行。
2. 开车穿过一平方的草地需要 1 天。
3. 驾车穿过一平方的沙漠需要 1.5 天。
4. 在路上行驶每个路段需要 0.5 天。

现在，您有一个简单的图表，您可以找到距离不超过 5 天的所有位置 with Dijkstra's algorithm .