java - 计算最短网格距离

Question

Consider a city where the streets are perfectly laid out to form an infinite square grid. In this city finding the shortest path between two given points (an origin and a destination) is much easier than in other more complex cities. As a new Uber developer, you are tasked to create an algorithm that does this calculation.

Given user's departure and destination coordinates, each of them located on some street, find the length of the shortest route between them assuming that cars can only move along the streets. You are guaranteed that at least one of the coordinates is an integer.

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

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坐标之间的绝对值，然后将它们相加即可。这称为 Manhattan distance .

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

对于 double ，除了一种情况外，几乎完全一样。以下是一些可能性:

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

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

例如，如果输入是:{x: 0.5, y: 2} 和 {x: 0.5, y: 3} 你将不得不水平移动，垂直，然后再次水平向后以到达目的地。这与 {x: 0.5, y: 2} 和 {x: 1.5, y: 3} 的输入不同，因为不需要在相同的方向上向后移动轴。

所以您可以在所有情况下使用正常算法除了 X 或 Y 都具有浮点值且具有相同的floor 的情况 -教育值(value)。

您的代码应如下所示。

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))