递归宽度优先搜索矩阵，最快路径（每个矩阵点将花费时间）

Question

考虑下面这个矩阵，我应该从一个给定点（用户输入）到另一个（用户输入）。例如，可以是海洋[1][1]到海洋[2][4]。我需要找到到终点的最短路径。现在，通过实现BFS可以很容易地解决这个问题。但在这种情况下，情况就不那么简单了。考虑矩阵中的每个点，它们都有不同的值。在

我要驾驶一艘船从起点到终点。对于矩阵中的每一个点，我都有不同的风况，这将导致船通过某些点的速度更快，通过其他点的速度较慢。每个点的速度，以及通过一个点所需的时间取决于我从哪个方向进入这些点。在

这意味着我只能知道何时通过一个点，而不是从一开始测试。在

说到这里，我的目标不再是找到“最短”的路径，而是最快的路径。在

另外还有一个变量需要考虑。我可以在8个方向移动，水平，横向和垂直（北，东北，东，东南等…）。水平移动是sqrt（2）个移动单位，移动其他方向=1个移动单位。在

因此，计算在一个点上花费的时间，你可以选择进入该点的方向（知道你移动了多少个单位）以及该点的速度（根据风条件计算）。在

为了找到最快的路径，我应该使用“递归宽度优先搜索”，这是作为一个指示。在

我知道如何编写BFS以找到最短路径，但我不知道从哪里开始编写递归BFS，以及如何考虑所有变量（时间等）

有什么线索可以告诉我从哪里收集信息吗？另外，这听起来是一种逻辑方法来做递归的BFS吗？在

这是一个矩阵示例：考虑所有带有“0”的点都有不同的值（通过该点所需的时间）。在

ocean =[[0,0,0,0,0,0], 

        [0,0,0,0,0,0],

        [0,0,0,0,0,0],

        [0,0,0,0,0,0],

        [0,0,0,0,0,0],

        [0,0,0,0,0,0]]

Answer 1

您可以将矩阵表示为一个图（必要时扩展节点数），然后使用Bellman-Ford查找最短路径。 我说的是最短路径，因为如果你定义好你的图和它的节点的权重，计算最快路径就等于计算最短路径。在

使用Bellman Ford，节点上也可以有负权重（例如，对于那些可以提高速度的节点），否则可以使用Dijkstra或BFS的一个变体来表示加权图。在