计算最短网格距离

Question

考虑一个城市，街道完美布局，形成无限的方形网格。在这个城市中，找到两个给定点（起点和终点）之间的最短路径比在其他更复杂的城市中容易得多。作为新的 Uber 开发人员，您的任务是创建一个执行此计算的算法。

给定用户的出发地和目的地坐标，每个坐标都位于某条街道上，假设汽车只能沿着街道移动，则找到它们之间的最短路线的长度。保证至少有一个坐标是整数。

我正在努力弄清楚这里的逻辑。有很多情况，我不知道如何容纳它们。这就是我到目前为止所拥有的

double perfectCity(double[] departure, double[] destination) {
    double yDist = Math.abs(destination[1]-departure[1]);
    double xDist = Math.abs(departure[1] - departure[0] + departure[1]-destination[0]);
    return xDist + yDist;
}

Answer 1

如果输入是整数，算法非常简单，只需找到 x 和 y 坐标之间的绝对值，然后将它们相加即可。这称为曼哈顿距离。

int distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);

对于双打来说，除了一种情况之外，几乎完全相同。以下是一些可能性：

1. 两个点都有整数坐标
2. 一个点有整数坐标，另一点只有一个整数坐标
3. 两个点只有一个整数坐标，但它们位于不同的轴上。
4. 两个点只有一个整数坐标，并且位于同一轴上。

可能性 1-3 使用与用整数​​查找距离相同的算法都可以正常工作，除了 #4 可能具有共同的轴位于同一块上的可能性。

例如，如果输入是：{x: 0.5, y: 2}并且{x: 0.5, y: 3}您必须水平移动、垂直移动，然后再次水平向后移动才能到达目的地。这与{x: 0.5, y: 2}和的输入不同{x: 1.5, y: 3}，因为不需要在同一轴上向后移动。

因此，除了X 或 Y 都具有浮点值且具有相同 -ed 值的情况之外，您可以在所有情况下使用正常算法floor。

您的代码应该如下所示。

import static java.lang.Math.*;

public static double perfectCity(double x1, double y1, double x2, double y2) {
    double xDist = abs(x1 - x2);
    double yDist = abs(y1 - y2);
    if (floor(x1) != x1 && floor(x2) != x2 &&        // both Xs are doubles
        floor(x1) == floor(x2) &&                    // on the same block
        y1 != y2) {                                  // not on the same street
        xDist = min(abs(x1 - floor(x1) + x2 - floor(x2)),
                    abs(x1 - ceil(x1)  + x2 - ceil(x2)));
    } else if (floor(y1) != y1 && floor(y2) != y2 && // both Ys are doubles
               floor(y1) == floor(y2) &&             // on the same block
               x1 != x2) {                           // not on the same street
        yDist = min(abs(y1 - floor(y1) + y2 - floor(y2)),
                    abs(y1 - ceil(y1)  + y2 - ceil(y2)));
    }
    return xDist + yDist;
}

通过使用辅助函数单独计算每个轴可以进一步简化这一过程。

public static double perfectCity(double x1, double y1, double x2, double y2) {
    return travelOnAxis(x1, x2, y1 == y2) + travelOnAxis(y1, y2, x1 == x2);
}

private static double travelOnAxis(double from, double to, boolean travelIsStraight) {
    if (Math.floor(from) == Math.floor(to) && !travelIsStraight) {
        double dist = Math.abs((from % 1) + (to % 1));
        return Math.min(dist, 2 - dist);
    } else {
        return Math.abs(from - to);
    }
}

我在这里使用了这个技巧，2 - dist因为它与计算相同

Math.abs((1 - (from % 1)) + (1 - (to % 1)))

这与以下相同

Math.abs(from - Math.ceil(from) + to - Math.ceil(to))