вычисление кратчайшего расстояния сетки

Алгоритм очень прост, если входные данные являются целыми числами, просто найдите абсолютное значение между координатами 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 имеют значения с плавающей запятой и имеют одно и то же значение floored.

Ваш код должен выглядеть примерно так.

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

Если это квадратная сетка, вы можете рассматривать координаты x и y отдельно; минимальное расстояние равно сумме минимальных расстояний в двух направлениях.

В p-направлении (либо x, либо y) вы должны двигаться из p1 в p2. Из p1 вы можете либо перейти к floor(p1), либо к ceil(p1), чтобы добраться до дороги (которая может быть равна, если p1 — целое число); оттуда вы можете перейти либо к floor(p2), либо к ceil(p2), дороге, на которой находится p2; оттуда вы можете перейти к p2.

Таким образом, минимальное расстояние в направлении p равно

min(abs(p1 - ceil(p1) ) + abs(ceil(p1)  - floor(p2)) + abs(floor(p2) - p2),  # (1)
    abs(p1 - floor(p1)) + abs(floor(p1) - ceil(p2) ) + abs(ceil(p2)  - p2),  # (2)
    abs(p1 - floor(p1)) + abs(floor(p1) - floor(p2)) + abs(floor(p2) - p2),  # (3)
    abs(p1 - ceil(p1) ) + abs(ceil(p1)  - ceil(p2) ) + abs(ceil(p2)  - p2))  # (4)

Таким образом, вы можете просто рассчитать это независимо для направлений x и y и добавить.

Чтобы проиллюстрировать это (сокращение floor и ceil как f и p соответственно):

f(p1) p1  c(p1)
  +---O>>>>+>>>>>>>>+
                    .
                    .
                    +>>>O----+
                  f(p2) p2  c(p2)

--------------------------------> p axis

Кратчайший маршрут здесь обозначен цифрой >. Маршруты . находятся на кратчайшем маршруте, но, поскольку эта часть маршрута ортогональна направлению p, она "не учитывается" при расчете минимального расстояния в этом направлении.

Минимальный маршрут, показанный здесь, p1 -> c(p1) -> f(p2) -> p2, соответствует описанному выше варианту 1.

Нетрудно представить, как поменять местами p1 и p2, и в этом случае минимальный маршрут должен идти от p1 ->f(p1) -> c(p2) -> p2 (вариант 2).

Случай pN == f(pN) == c(pN) не сильно отличается; тогда часть выражения abs(pN - f(pN)) или abs(pN - c(pN)) равна нулю.

Немного другой случай, когда f(p1) == f(p2):

f(p1) p1  c(p1)          f(p1) p1  c(p1)
  +---O>>>>+               +<<<O----+
           .               .
           .               .
  +-----O<<+               +>>>>>O--+
 f(p2) p2  c(p2)          f(p2) p2  c(p2)

--------------------------------> p axis

В этом случае минимальный маршрут может быть либо p1 -> f(p1) -> f(p2) -> p2, либо p1 -> c(p1) -> c(p2) -> p2 (это случаи 3 и 4 соответственно).

Как упоминалось в 4castle, проблема тривиальна, если для ввода рассматриваются только целые числа. В этом случае вам никогда не придется «двигаться назад» после того, как вы «двинулись вперед», поскольку вы всегда будете достигать своей цели одним движением.

Но поскольку максимум необходимо учитывать одно число с плавающей запятой для каждого пункта отправления/пункта назначения, нам необходимо рассмотреть 3 случая (предупреждение: длинное объяснение). Ниже приведена реализация python2 с пояснениями.

1. x координаты отправления и пункта назначения одинаковы и не являются числами с плавающей запятой. В этом случае кратчайшее расстояние — это просто абсолютная разница между координатами y. Та же логика применима и в обратную сторону.

   import math
   class Location():
       def __init__(self, cord):
           self.x = cord[0]
           self.y = cord[1]
   
   def perfectCity(departure, destination):
       l1 = Location(departure)
       l2 = Location(destination)
   
       if l1.x == l2.x and float(l1.x).is_integer() and float(l2.x).is_integer():
           return abs(l1.y-l2.y)
       if l1.y == l2.y and float(l1.y).is_integer() and float(l2.y).is_integer():
           return abs(l1.x-l2.x)
   

2. Если одна из координат в departure представляет собой число с плавающей запятой, тогда:

   • If x co-ordinate is floating point, we can move backwards(round down) or move front(round up).
   • Если координата y является плавающей запятой, мы можем двигаться либо вниз (округление вниз), либо вверх (округление вверх).
   • Приведенная выше логика должна работать даже при отсутствии координат с плавающей запятой, поскольку мы перемещаемся в любом направлении на ноль единиц.
   • Как только мы вычислим их, мы просто выберем минимум среди приведенных ниже,

return min(calc_round_up_dist(l1, l2), cal_round_down_dist(l1, l2))

Lets take an example of (0.4, 1) and (0.9, 3) для расчетов ниже.

3. При расчете round_up нам нужно рассчитать 3 расстояния:

   • round_up_distance: difference between the rounded up value of the floating point co-ordinate and the original floating point co-ordinate. We return zero if there is no floating point co-ordinate. 1 - 0.4 = 0.6 in the above example
   • разница non_floating_point: разница между координатой отправления без плавающей запятой и соответствующей координатой пункта назначения ( обратите внимание, что это может быть с плавающей запятой или не с плавающей запятой abs(3-1) = 2 in the above example
   • Разница между аналогом отправления с плавающей запятой в координате пункта назначения 0.9 in the above case и новым значением числа с плавающей запятой отправления после округления, 0.4 + 0.6(this is the round_up distance) = 1.0, т. е. abs(0.9 - 1.0) = 0.1
   • Складывая все 3 выше, мы получаем 0.6 + 2 + .1 = 2.7, что является кратчайшим расстоянием.

   • Для округления в меньшую сторону необходимо произвести соответствующий расчет. И мы выбираем минимум среди обоих. Код для round_up и round_down приведен ниже:

     import math
     class Location():
         def __init__(self, cord):
             self.x = cord[0]
             self.y = cord[1]
     
         def floating_point_round_up(self):
             if not float(self.x).is_integer():
                 return math.ceil(self.x) - self.x
             if not float(self.y).is_integer():
                 return math.ceil(self.y) - self.y
             return 0
     
         def floating_point_round_down(self):
             if not float(self.x).is_integer():
                 return self.x - math.floor(self.x)
             if not float(self.y).is_integer():
                 return self.y - math.floor(self.y)
             return 0
     
         def non_floating_point_diff(self, obj):
             if not float(self.x).is_integer():
                 return abs(self.y - obj.y)
             if not float(self.y).is_integer():
                 return abs(self.x - obj.x)
             return abs(self.y - obj.y)
     
         def floating_point_counterpart(self, obj):
             if not float(self.x).is_integer():
                 return obj.x
             if not float(self.y).is_integer():
                 return obj.y
             return obj.x
     
         def floating_point(self):
             if not float(self.x).is_integer():
                 return self.x
             if not float(self.y).is_integer():
                 return self.y
             return self.x
     

4. Функции округления вверх и вниз приведены ниже,

   def calc_round_up_dist(l1, l2):
       dist = l1.floating_point_round_up()
       diff = l1.non_floating_point_diff(l2)
       floating_point_counterpart = l1.floating_point_counterpart(l2)
       new_val = dist + l1.floating_point()
       return dist + diff + abs(new_val - floating_point_counterpart)
   
   def cal_round_down_dist(l1, l2):
       dist = l1.floating_point_round_down()
       diff = l1.non_floating_point_diff(l2)
       floating_point_counterpart = l1.floating_point_counterpart(l2)
       new_val = l1.floating_point() - dist
       return dist + diff + abs(floating_point_counterpart - new_val)
   

5. Наконец, основная функция, которая вызывает вышеупомянутые методы,

   def perfectCity(departure, destination):
       l1 = Location(departure)
       l2 = Location(destination)
   
       if l1.x == l2.x and float(l1.x).is_integer() and float(l2.x).is_integer():
           return abs(l1.y-l2.y)
       if l1.y == l2.y and float(l1.y).is_integer() and float(l2.y).is_integer():
           return abs(l1.x-l2.x)
   
       return min(calc_round_up_dist(l1, l2), cal_round_down_dist(l1, l2))