计算2点之间的网格距离

提问于 2024-04-26T03:30:14+08:00

浏览次

11

我需要计算2点之间的网格距离 . 允许的运动是水平的和垂直的，以及与下一个邻居的对角线（所以45度旋转） .

所以曼哈顿距离不是一个选择 . 欧几里德距离也不是一个选项，因为它不能沿着网格正确移动，这可能导致一个低值（如红线所示） .

我希望得到的距离就像它从一个细胞移动到另一个细胞的绿线一样 .

公式最好是快速的 .

enter image description here

1 回答

11
这很简单：
- 您沿对角线朝目标移动，直到您位于同一行或同一列 . 这将是min（dx，dy）步骤 .
我们称之为d（对角线步骤）
- 然后你朝着球门的直线前进 . 这将是max（dx，dy） - d步 .
我们称之为s（直接步骤）
- 距离为√2×d s .
在代码中：
```
double distance(int x1, int y1, int x2, int y2) {
    int dx = abs(x2 - x1);
    int dy = abs(y2 - y1);

    int min = min(dx, dy);
    int max = max(dx, dy);

    int diagonalSteps = min;
    int straightSteps = max - min;

    return sqrt(2) * diagonalSteps + straightSteps;
}
```
回复于 2024-04-26T03:30:14+08:00

相关问题