首页>Program>source

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

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

在此地图上 意思是 spacespace -平台, _ -我们从这里开始的平台 -目的地.在这张地图上行走的怪物可以 SD . 到达 jump up, down的可能方法 来自 move to the left or to the right 通过怪物是:

D

或者它可能到达 S 通过这种方式:

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

因此,到达目的地点的组合可以通过多种方式改变,但要点是,在第一种情况下,怪物做出的最大跳跃距离D ,因为以这种方式,两个平台之间的最大距离是 _ _ _ D _ _ _ + _ _ + _ S _ _ _ _ _ .在第二种情况下,怪物很快到达目的地,但他飞跃了距离 1 .怪物的主要目标是到达目的地,而不要跳得太远(越小越好),因此,首选第一种方法.问题是我应该使用哪种算法来找到最大跳跃距离最小的方式?

我考虑过两种方法:

  1. 强力,但是当平台数为 1时会很不方便 ;
  2. 以某种方式将此矩阵转换为图形,其中每个平台均表示为图形的节点,并且通过跳跃距离表示边缘,并找到最小的生成树,但首先我不知道该如何在其中创建相邻矩阵 方式,并且将是正确的方式。
2
最新回答
  • 3天前
    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
    

    其余的是最短路径问题.使用Dijkstra的算法查找 start之间的最短路径 和 dest 节点。

  • 3天前
    2 #

    感谢您在上面发布,我决定完成此想法并获得此代码,对于我得到的测试用例,它工作正常.因此,想法是:

    根据给定的平台图,有必要创建一个图,其中一个节点表示一个平台(包括起始平台和目标平台),并且节点之间的边缘表示为它们之间的距离;

    形成图形时,您的目标是找到最小的生成树并找到该树中边缘的最大权重-这就是答案。 代码很大,请在我的github上检查! 注意 1 意味着平台, 2 意味着开始和 3 是目的地:

    检查此github链接!

  • java:Gui可视化递归回溯数独
  • c#:如何在Entity Framework Core 5中使用自定义列进行SQL查询