时间戳

首页 > 解决方案 > 找到这样一种方式，即在途中跳跃的最大距离可能是最小的

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

问题描述

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

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

在这张地图space中space，_- 平台，S- 我们开始的平台，D- 目的地点。在这张地图上行走的怪物可以向上、向下或向左或向右移动。怪物到达的可能方式D是：S

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

D或者它可能以这种方式到达：

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

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

我想过两种方法：

  1. 蛮力的，但是平台数量多的时候会很不方便=N*M；
  2. 不知何故将此矩阵转移到图中，其中每个平台都表示为图的节点，边由跳跃距离表示并找到最小生成树，但首先我不知道如何以这种方式创建相邻矩阵并将这种方式是正确的。

标签： algorithmgraphdynamic-programminggreedy

解决方案

解析地图并查找节点：

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

剩下的是最短路径问题。使用Dijkstra 算法找到start和dest节点之间的最短路径。

推荐阅读