给出最大长度的最长路径

Question

我需要帮助.

我会尽量解释尽可能完美.

假设我有一个2d网格,这是我的"世界".

网格看起来像这样:

灰色方块是草.绿色方块是道路.橙色方块是沙漠.

中间的蓝色方块是我的车.我的车的射程限制为5格.我想找到并突出显示我可以达到的最大范围或更小的所有方格.

在灰色广场上行驶需要1个范围.没有什么花哨.但是,驾驶绿色方块可以获得+0,5的范围.这意味着,如果你开出的前两个方格是绿色,那么你的最大范围是突然的6.在橙色方格上行驶会给你一个-0,5的范围惩罚.这意味着如果您通过的前2个方格是橙色,则最大范围为4.

所以基本上,驾驶到一个广场,花费你1个范围,但根据广场,它可以给你额外的范围或更小的范围.

考虑奖金,探索所有路径.会使我的汽车最外部的范围看起来像这样:

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

很长的问题,但我如何实现这一目标？

我先研究了广度和深度等等,但由于我可以在同一个广场上走几条路线,所以我不能在第一时间将其标记为"已访问",然后再回到它上面？

对此的帮助将大大加以理解.

感谢您一直在这里阅读.

/ E

Answer 1

你可以更容易地代表你的模型,所有这些都是在成本而不是奖金方面.

1. 你有5天的旅行时间.
2. 开车穿过一个方形的草需要1天.
3. 开车穿过沙漠的一个广场需要1.5天.
4. 每个路段在路上行驶需要0.5天.

现在,您有一个简单的图表,您可以使用Dijkstra的算法找到距离不超过5天的所有位置.