将递归算法转化为广度优先队列

Question

因此，我正在使用一门“课程”。整个赛道充满了坐标。每个坐标都有允许移动的属性(#left #right #up #down)。课程建立在一个坐标系上，左边是x-1，右边是x+1，向上是y-1，向下是y+1。

我的目标是得到每个可达坐标的最短距离。距离由距起点的移动次数(参数中提供的路线的起点坐标)定义。所以从(0,0)到(1,2)的距离是3.1向右，向下是2。我最初使用递归解决了这个问题：

答:不是尽可能深入地遍历每个路径，而是使用一个数组一次遍历每个差异中的每个路径

Answer 1

将您的问题想象成一个无向图，其中节点是坐标，其中每对(不同的)节点[x0,y0]和[x1,y1]在以下情况下是“相邻的”：

[x0-x1].abs <= 1 && [y0-y1].abs <= 1

如果两个节点相邻，则它们由无向链路连接，在这种情况下，该链路的长度为1。如果两个节点通过节点和链路的路径连接，则它们之间的距离等于路径上链路的长度之和(即路径中的链路数)。

您可以使用一种算法来计算无向图中所有节点对之间的最短路径，例如Floyd-Warshall algorithm (它也适用于有向图)，从而找到所有坐标对之间的最短距离。

Floyd-Warshall将不相邻的节点对视为由无限长的链路连接(这可以实现为适当的大数字)。如果给定的一对节点之间的最短路径的长度被发现是“无限的”，那么您就知道这些节点是没有连接的(即，坐标之间没有路径)。