寻找最短路径算法

Question

首先，感谢您抽出宝贵时间阅读本文post。

Problem:

Find the shortest path from i to j (i != j; i, j >= 0) from a given array, whereas you can only move left, right, or go to any element which has the same value to current element.

示例： 我有一个包含 9 个数字的数组：int arr[9] = {7, 2, 5, 3, 8, 6, 9, 7, 0}； int i = 1, j = 6;

根据上面的声明，我想从 arr[i] 到 arr[j] （2 到 9）然后最短路径是 arr[1](2) -> arr[0](1st 7) -> arr[7](2nd 7) -> arr[6](9)（总步数：3）

更多示例：

int arr[9] = {7, 2, 5, 3, 8, 6, 9, 7, 0}； int i = 7, j = 8; 步骤：1 (7 -> 8)

int arr[9] = {8, 2, 0, 3, 8, 6, 9, 7, 0}； int i = 0, j = 8; 步骤：3 (0 -> 1 -> 2 -> 8)

int arr[9] = {1, 5, 7, 3, 4, 22, 9, 8, 6}； int i = 2, j = 7; 步骤：5 (2 -> 3 -> 4 -> 5 -> 6 -> 7)

我试图遍历数组中的所有元素（i & j 除外）以查看是否有任何元素具有相同的值并且最接近 j，但我最终要处理更多的案例。希望大家能帮帮我，先谢谢了！

Answer 1

好的，最简单的方法是：

1. 创建另一个数组，将其命名为 distance 并用值 -1 填充它。
2. 设置distance[i] = 0，因为它可以自由地从元素移动到自身
3. 循环遍历 distance 并且对于每个不是 -1 的现有数字，用当前元素的数字 + 1 填充左侧和右侧的元素（仅当left/right 上的元素等于 -1)
4. 对于新填充的元素，在array中找到具有相同值的元素，并将它们的distance设置为与步骤3相同的值。

一旦你循环了足够多的次数，你就会得到数组 distance 完全填充，这将告诉你任何元素距离元素 array[i].

有多远

如果您只需要 distance[j] 并且您已经找到它，您可以提前退出循环。