2

我既是这个网站的新手，也是 C 的新手。我需要一个程序来找到所有点的平均“跳跃”。

在此处输入图像描述

这个想法是这样的：找到从 1 到 2、1 到 3、1 到 4 ... 1 到 9 的“跳跃”距离，或者找到 2 到 1、2 到 3、2 到 4、2 到 5 等。

在第一行执行它们很简单，只需 (2-1) 或 (3-1) 即可获得正确的数字。但如果我想找到 1 到 4 或 1 到 8 之间的距离，那我完全不知道。矩阵的维度应该是可变的。但我只需要 3x3 矩阵的帮助。

任何人都可以告诉我如何找到它？

跳跃是指从一个点垂直或水平移动到另一个点。从 1 到 2 = 1，从 1 到 9 = 4（仅最短路径）

4

4 回答 4

6

这类问题上“距离”的定义总是很棘手。

想象一下，这些点是田野上的标记，你可以在上面自由走动。然后，您可以选择从一个点到另一个点的任何路径。那么最短的路线将是一条直线；它的长度将是连接点的向量的长度，这恰好是两个点位置之间的差向量。这个长度可以借助毕达哥拉定理来计算：dist = sqrt((x2-x1)^2 + (y2-y1)^2)。这被称为点之间的欧几里得距离。

现在想象你在一个城市，每个点都是一座建筑物。你不能走过建筑物，所以唯一的选择是上/下或左/右。然后，最短距离由差向量的分量之和给出；这是数学上的说法，“走 2 个街区，然后向左走 1 个街区”意味着步行 3 个街区的距离：dist = abs(x2-x1) + abs(y2-y1). 这被称为点之间的曼哈顿距离。

但是，在您的问题中，似乎唯一可能的移动是跳到相邻点，一步，允许对角线。然后问题变得有点棘手，因为路径非常不规则。您需要一些图论，这在使用链接元素或“节点”建模问题时非常有用。每个点都是一个节点，连接到它们的邻居，问题是找到到另一个给定点的最短路径。如果跳跃有不同的权重（例如，对角线跳跃更难），解决这个问题的简单方法是使用 Dijkstra 算法；Wikipedia上有关实施的更多详细信息。

如果成本始终相同，那么问题就归结为计算从源点到目标点的广度优先搜索中的跳跃次数。

于 2013-03-02T21:31:38.077 回答
3

让我们定义“跳跃”距离：“从 A 点 [A x ,A y ] 到 B 点 [B x ,B y ] 所需的跳数。”

现在可以有两种方式允许跳跃：

  1. 水平/垂直
    在这种情况下，您可以上/下或左/右。由于您必须独立移动 X 轴和 Y 轴，因此您的答案是：
    jumpDistance = abs(Bx - Ax) + abs(By - Ay);

  2. 水平/垂直和对角线
    在这种情况下，您也可以向上/向下或向左/向右和对角线。不同之处Case 1在于，现在您只需一次跳跃即可同时更改 X 轴和 Y 轴。你现在的答案是：
    jumpDistance = Max(abs(Bx - Ax),abs(By - Ay));

于 2015-10-20T19:30:31.523 回答
2

“跳跃距离”的定义是什么？

如果你的意思是一个人从 M 到 N 需要跳多少次，如果他只能垂直和水平跳跃，那么一种可能性可以：

dist = abs(x2 - x1) + abs(y2 - y1);

例如 1 到 9 之间的跳跃距离是：|3-1|+|3-1| = 4

于 2013-03-02T21:20:48.333 回答
0

有两种计算跳跃距离的方法。1）当只允许水平和垂直移动时，在这种情况下，您需要做的就是在两点之间形成一个矩形并计算两个相邻边的长度。就像如果你想从 1 移动到 9，那么首先从 1 移动到 3，然后从 3 移动到 9。（将其转换为代码）2）当所有八个方向的移动都被允许时，事情就变得棘手了。就像你想从 1 移到 6 假设一样。您需要做的是，您必须从 1 到 5。然后从 5 到 6。在代码中执行此操作的方法是找到 x 和 y 坐标差之间的最大值。在此示例中，在 x 坐标中，差异为 2 (3-1)，在 y 坐标中，差异为 1 (2-1)。所以这个最大值是2。所以这就是答案。（转换为代码）

于 2020-03-24T07:04:27.757 回答