找到这样一种方式，即在途中跳跃的最大距离可能最小

Question

有一个可以放置在不同高度的平台。例如，这些地图显示了平台的放置方式（在程序中显示为矩阵 NxM, |N|, |M| <= 100

      _ _ _    
    D _   _ _  
            _ _
              _
    S _ _ _ _ _

在这张地图中space表示space，_-平台，S-我们出发的平台，D-目的地。在此地图上行走的怪物可以跳上跳下或向左或向右移动。怪物从 S 到达 D 的可能方法是：

  + + +    
D +   + +  
        + +
          +
S + + + + +

或者可以这样到达D:

      _ _ _    
    D _   _ _  
    +       _ _
    +         _
    S _ _ _ _ _

因此，到达目的地点的组合可以有多种方式，但要点是在第一种情况下，怪物跳跃的最大距离是1，因为这样两个平台之间的最大距离是1。在第二种情况下，怪物很快就到达了目的地，但他跳跃了距离 2。怪物的主要目标是到达目的地而不是大跳（尽可能小），因此首选第一种方式。问题是我应该使用什么算法来找到最大跳跃距离最小的方法？

我想过两种办法：

蛮力，但当平台数为=N*M;
以某种方式将这个矩阵转换成图形，其中每个平台都表示为图形的节点，边缘由跳跃距离表示并找到最小生成树但首先我不知道如何创建相邻矩阵以这种方式并将以这种方式正确。

Answer 1

要解析地图并查找节点：

for i from 1 to N
    for j from 1 to M
        if map(i, j) == 'S' 
            nodes.add(i, j);
            start = nodes.Count;
        elseif map(i, j) == 'D' 
            nodes.add(i, j);
            dest = nodes.Count;
        elseif map(i, j) == '_'
            nodes.add(i, j);
        end
    end
end

在上面的伪代码中，我假设 nodes.add(i, j) 添加一个带有 node.x = 1 和 node.y = j 的新节点到节点列表中。

然后，构造邻接矩阵：

n = nodes.Count;
adj = n by n matrix, filled with +inf;
for i from 1 to n
    for j from i + 1 to n
       if (nodes[i].x == nodes[j].x) || (nodes[i].y == nodes[j].y)
           adj(i, j) = abs(nodes[i].x - nodes[j].x) +
               abs(nodes[i].y - nodes[j].y);
       end
    end
end

剩下的就是Shortest Path Problem. Use Dijkstra's algorithm求start和dest节点之间的最短路径

Answer 2

感谢上面的 post，我决定完成这个想法并获得这段代码，对于我得到的测试用例，它工作正常。所以，想法是：

根据给定的平台地图，有必要创建一个图表，其中一个节点表示一个平台（包括起始平台和目标平台），节点之间的边表示为它们之间的距离；
当你形成图时，你的目标是找到最小生成树并找到这棵树中边的最大权重 - 这就是答案。代码很大，请在我的 github 上查看！注意1表示平台，2表示开始，3表示目的地：

Check this github link out!

找到这样一种方式，即在途中跳跃的最大距离可能最小

Find the such way that maximum distance of a jump in the way is possible minimal

algorithm

graph

dynamic-programming

greedy