二维阵列角点到角点的最小路径

Question

我正在处理一个问题，我试图从左上角，即（0,0），到右下角，或（m-1，n-1），输入m x n 2D数组。此外，数组的每个元素表示可以从该方块进行何种跳跃。

例如，一个表看起来像：

1 2 1

1 1 1

1 1 1

最小路径为3，因为您可以从（0,0）开始，向右跳1个方块到（0,1），向下跳2个方块到（2,1），然后向右跳1个方块到（2,2）的目标。

我当前的实现使用BFS，在BFS中，我将每个未访问的连接方块推到一个队列中，直到到达拐角处或无法继续；在此过程中，我更新了一个单独的2D数组，该数组包含从起始方块到达实际板上特定坐标所需的移动次数。

我的代码适用于我抛出的许多测试，但对于一些看似随机的测试用例，它返回了错误的移动次数（比实际移动次数高出很多）。我不知道为什么会这样！任何关于我可能出错的地方的建议都将不胜感激。

Answer 1

我认为问题在于，您正在更新distanceArray，而没有将该正方形设置为已访问（这通常会防止在distanceArray中覆盖该正方形），并且仅在该正方形到达队列顶部时才将其标记为已访问。这意味着队列前面的另一条路径可能会在标记为已访问之前覆盖该距离。

下面是这个问题的一个例子

Board:
1 1 1 1  
1 2 1 1  
1 1 1 1  
1 2 1 1  

Queue:   0,0 1,0 0,1 2,0 1,1 1,1 0,2 3,0 2,1 *3,1* 1,3 1,2 0,3 *3,1*   
Distance: 0   1   1   2   2   2   2   3   3   *3*   3   3   3   *4*  

正如您所看到的，访问1,1会将3,1排成距离为3的队列，但访问3,0也会将3,1排成队列，并将其距离覆盖为4，因为3,1尚未到达队列的顶部，并且尚未被视为已访问。

有多种方法可以解决这个问题。最简单的方法可能是在您加入时将其设置为已访问。然而，这在你的确切情况下是不太可行的，因为你使用董事会来标记访问。因此，您可能希望将访问过的信息存储在其他地方。您可以将板方块从int更改为一个对象，该对象还保存它们访问过的信息以及它们的步长值（同时添加它们的最短路径距离）。
或者，如果你不想重写很多以前的代码，你可以制作另一个2D数组来存储访问过的信息，类似于您的距离数组。

您还将向队列中添加两次east。这不应该引起任何问题，但无论如何都值得解决