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