二维数组从一个角到另一个角的最小路径
Smallest path from corner to corner of a 2D array
我正在解决一个问题，我试图从左上角，即 (0,0) 到右下角，或 (m - 1, n - 1)，输入 m x n 二维数组。此外，数组的每个元素代表可以从该方块进行什么样的跳跃。
例如，table 看起来像：
1 2 1
1 1 1
1 1 1
最小路径为 3，因为您可以从 (0,0) 向右跳 1 格到 (0,1)，向下跳 2 格到 (2, 1)，然后跳 1 格到达 (2, 2) 目的地的权利。
我目前的实现使用 BFS，我将每个未访问的连接方块推入队列，直到我到达角落或无法继续；一路上，我更新了一个单独的二维数组，其中包含从起始方块到达实际板上的特定坐标所需的移动次数。
我的代码适用于我对其进行的许多测试，但对于一些看似随机的测试用例，它 returns 移动次数错误（比实际次数高很多）。我不知道为什么会这样！任何关于我可能哪里出错的建议都将不胜感激。
我认为问题是您在更新 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 的 3,1 入队，但随后访问 3,0 也会使 3,1 入队并将其距离改写为 4，因为 3,1 尚未到达顶部队列中，尚未被视为已访问。
有多种方法可以解决这个问题。最简单的可能是在排队时将其设置为已访问。但是，这在您的具体情况下不太可行，因为您使用板来标记已访问。因此，您可能希望将访问过的信息存储在别处。您可以将棋盘方块从 int 更改为一个对象，该对象还包含它们的访问信息以及它们的步长值（当您在它处添加它们的最短路径距离时）。
或者，如果您不想重写很多以前的代码，您可以制作另一个二维数组来存储访问过的信息，类似于您的 distanceArray。
您还两次将 east 添加到队列中。这应该不会造成任何问题，但无论如何都值得解决
我正在解决一个问题，我试图从左上角，即 (0,0) 到右下角，或 (m - 1, n - 1)，输入 m x n 二维数组。此外，数组的每个元素代表可以从该方块进行什么样的跳跃。
例如，table 看起来像：
1 2 1
1 1 1
1 1 1
最小路径为 3，因为您可以从 (0,0) 向右跳 1 格到 (0,1)，向下跳 2 格到 (2, 1)，然后跳 1 格到达 (2, 2) 目的地的权利。
我目前的实现使用 BFS，我将每个未访问的连接方块推入队列，直到我到达角落或无法继续；一路上，我更新了一个单独的二维数组，其中包含从起始方块到达实际板上的特定坐标所需的移动次数。
我的代码适用于我对其进行的许多测试，但对于一些看似随机的测试用例，它 returns 移动次数错误（比实际次数高很多）。我不知道为什么会这样！任何关于我可能哪里出错的建议都将不胜感激。
我认为问题是您在更新 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 的 3,1 入队，但随后访问 3,0 也会使 3,1 入队并将其距离改写为 4，因为 3,1 尚未到达顶部队列中，尚未被视为已访问。
有多种方法可以解决这个问题。最简单的可能是在排队时将其设置为已访问。但是，这在您的具体情况下不太可行，因为您使用板来标记已访问。因此，您可能希望将访问过的信息存储在别处。您可以将棋盘方块从 int 更改为一个对象，该对象还包含它们的访问信息以及它们的步长值（当您在它处添加它们的最短路径距离时）。
或者，如果您不想重写很多以前的代码，您可以制作另一个二维数组来存储访问过的信息，类似于您的 distanceArray。
您还两次将 east 添加到队列中。这应该不会造成任何问题，但无论如何都值得解决