Вы когда-нибудь сталкивались со сценарием, когда вам нужно было найти ближайшую действительную точку на сетке или структуре, напоминающей шахматную доску? Возможно, вы начинающий программист, желающий расширить свои навыки решения проблем.

В этом сообщении блога мы рассмотрим концепцию Манхэттенского расстояния и продемонстрируем, как использовать ее для поиска ближайшей допустимой точки к заданной позиции. Мы предоставим решения как на JavaScript, так и на Python, гарантируя доступность для разработчиков любого уровня подготовки.

Введение в Манхэттенское расстояние

Манхэттенское расстояние, также известное как расстояние L1 или расстояние такси, является фундаментальной концепцией решения задач на основе сетки.

Он измеряет расстояние между двумя точками в системе, напоминающей сетку, учитывая только горизонтальные и вертикальные движения.

Эта метрика расстояния названа в честь сетки улиц Манхэттена, где вы можете путешествовать только по этим линиям сетки — по горизонтали и вертикали.

Постановка задачи

Представьте, что вы находитесь в определенной точке сетки, представленной координатами (x, y). Ваша задача — найти действительную точку, ближайшую к вашему текущему местоположению, согласно Манхэттенскому расстоянию.

Точка считается действительной, если она имеет ту же координату X или Y, что и ваше текущее положение. Если несколько допустимых точек имеют одинаковое минимальное расстояние Манхэттена, мы возвращаем действительную точку с наименьшим индексом. Если действительные точки не найдены, мы возвращаем -1.

JavaScript-решение

Начнем с изучения решения этой проблемы на JavaScript:

// Define the current position (x, y) and an array of locations.
const x = 5;
const y = 1;
const locations = [[1, 1], [6, 2], [1, 5], [3, 1]];

// Function to find the closest valid point using Manhattan Distance.
function findClosestValidPoint(x, y, locations) {
  // Initialize variables to keep track of the minimum distance and index.
  let minDistance = Infinity;
  let minIndex = -1;

  // Iterate through the locations array.
  for (let i = 0; i < locations.length; i++) {
    // Extract the x and y coordinates of the current location.
    const [xi, yi] = locations[i];

    // Check if the current location shares the same x-coordinate or y-coordinate with the target position.
    if (xi === x || yi === y) {
      // Calculate the Manhattan Distance between the current location and the target position.
      const distance = Math.abs(x - xi) + Math.abs(y - yi);

      // Update the minimum distance and index if the current location is closer.
      if (distance < minDistance) {
        minDistance = distance;
        minIndex = i;
      }
    }
  }

  // Return the index of the closest valid point.
  return minIndex;
}

// Call the function to find the closest valid point and store the result in closestIndex.
const closestIndex = findClosestValidPoint(x, y, locations);

// Output the result.
console.log(closestIndex); // Output should be 3 (index of the closest valid point)

В JavaScript мы начинаем с определения текущей позиции (x, y) и массива местоположений. Затем мы перебираем местоположения, вычисляя Манхэттенское расстояние для каждой допустимой точки и отслеживая минимальное расстояние и индекс ближайшей допустимой точки.

Python-решение

Теперь давайте рассмотрим решение той же проблемы на Python:

# Define the current position (x, y) and an array of locations.
x = 5
y = 1
locations = [[1, 1], [6, 2], [1, 5], [3, 1]]

# Function to find the closest valid point using Manhattan Distance.
def find_closest_valid_point(x, y, locations):
    # Initialize variables to keep track of the minimum distance and index.
    min_distance = float('inf')
    min_index = -1

    # Iterate through the locations list using an index 'i'.
    for i in range(len(locations)):
        # Extract the x and y coordinates of the current location.
        xi, yi = locations[i]

        # Check if the current location shares the same x-coordinate or y-coordinate with the target position.
        if xi == x or yi == y:
            # Calculate the Manhattan Distance between the current location and the target position.
            distance = abs(x - xi) + abs(y - yi)

            # Update the minimum distance and index if the current location is closer.
            if distance < min_distance:
                min_distance = distance
                min_index = i

    # Return the index of the closest valid point.
    return min_index

# Call the function to find the closest valid point and store the result in closest_index.
closest_index = find_closest_valid_point(x, y, locations)

# Output the result.
print(closest_index)  # Output should be 3 (index of the closest valid point)

В Python мы используем аналогичный подход, перебирая местоположения и вычисляя Манхэттенское расстояние для каждой допустимой точки. Мы также отслеживаем минимальное расстояние и индекс ближайшей допустимой точки.

Заключение

Изучая больше алгоритмов и концепций, помните, что практика и настойчивость имеют решающее значение. Чем больше вы будете решать проблемы и совершенствовать свои навыки, тем увереннее и способнее вы станете как программист. Итак, продолжайте программировать, продолжайте исследовать и продолжать решать новые задачи. Приятного кодирования!

👋Привет! Если у вас есть острые вопросы или вы просто хотите поздороваться, не стесняйтесь — я на расстоянии всего лишь сообщения. 💬 Вы можете связаться со мной по адресу [email protected].

🤝 Кстати, я думаю, у нас одинаковый интерес к разработке программного обеспечения — давайте подключимся к LinkedIn! 💻