Лучшая точка встречи в двоичном 2D-массиве
Вам предоставляется двухмерная сетка значений 0 или 1, где каждая единица обозначает дом кого-то в группе. А группа из двух или более человек хочет встретиться и минимизировать общее расстояние путешествия. Они могут встретиться где угодно, значит, может быть дом или нет.
- Расстояние рассчитывается с использованием Манхэттенского расстояния, где расстояние (p1, p2) = | p2.x - p1.x | + | p2.y - p1.y |.
- Найдите общее расстояние, которое необходимо преодолеть, чтобы добраться до наилучшего места встречи (общее пройденное расстояние минимально).
Примеры:
Ввод: сетка [] [] = {{1, 0, 0, 0, 1},
{0, 0, 0, 0, 0},
{0, 0, 1, 0, 0}};
Выход: 6
Лучшее место встречи - (0, 2).
Общее пройденное расстояние 2 + 2 + 2 = 6
Ввод: сетка [3] [5] = {{1, 0, 1, 0, 1},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0}};
Выход: 11
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Шаги: -
1) Сохраните все горизонтальные и вертикальные положения всех членов группы.
2) Теперь отсортируйте его, чтобы найти минимальное среднее положение, которое будет лучшим местом встречи.
3) Найдите удаленность всех участников от наилучшего места встречи.
Например, на диаграмме выше горизонтальные позиции - это {0, 2, 0}, а вертикальные позиции - {0, 2, 4}. После сортировки обоих мы получаем {0, 0, 2} и {0, 2, 4}. Средняя точка - (0, 2).
Note : Even no. of 1’s have two middle points, then also it works. Two middle points means it have two best meeting points always. Both cases will give same distance. So we will consider only one best meeting point to avoid the more overhead, Because our aim is to find the distance only.
C++
/* C++ program to find best meeting point in 2D array*/#include <bits/stdc++.h>using namespace std;#define ROW 3#define COL 5 int minTotalDistance(int grid[][COL]) { if (ROW == 0 || COL == 0) return 0; vector<int> vertical; vector<int> horizontal; // Find all members home"s position for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (grid[i][j] == 1) { vertical.push_back(i); horizontal.push_back(j); } } } // Sort positions so we can find most // beneficial point sort(vertical.begin(),vertical.end()); sort(horizontal.begin(),horizontal.end()); // middle position will always beneficial // for all group members but it will be // sorted which we have alredy done int size = vertical.size()/2; int x = vertical[size]; int y = horizontal[size]; // Now find total distance from best meeting // point (x,y) using Manhattan Distance formula int distance = 0; for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) if (grid[i][j] == 1) distance += abs(x - i) + abs(y - j); return distance;} // Driver program to test above functionsint main() { int grid[ROW][COL] = {{1, 0, 1, 0, 1}, {0, 1, 0, 0, 0},{0, 1, 1, 0, 0}}; cout << minTotalDistance(grid); return 0;} |
Java
/* Java program to find best meeting point in 2D array*/import java.util.*; class GFG { static int ROW = 3;static int COL =5 ; static int minTotalDistance(int grid[][]){ if (ROW == 0 || COL == 0) return 0; Vector<Integer> vertical = new Vector<Integer>(); Vector<Integer> horizontal = new Vector<Integer>(); // Find all members home"s position for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (grid[i][j] == 1) { vertical.add(i); horizontal.add(j); } } } // Sort positions so we can find most // beneficial point Collections.sort(vertical); Collections.sort(horizontal); // middle position will always beneficial // for all group members but it will be // sorted which we have alredy done int size = vertical.size() / 2; int x = vertical.get(size); int y = horizontal.get(size); // Now find total distance from best meeting // point (x,y) using Manhattan Distance formula int distance = 0; for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) if (grid[i][j] == 1) distance += Math.abs(x - i) + Math.abs(y - j); return distance; } // Driver codepublic static void main(String[] args) { int grid[][] = {{1, 0, 1, 0, 1}, {0, 1, 0, 0, 0}, {0, 1, 1, 0, 0}}; System.out.println(minTotalDistance(grid));}} // This code is contributed by 29AjayKumar |
Python3
# Python program to find best meeting point in 2D arrayROW = 3COL = 5 def minTotalDistance(grid: list) -> int: if ROW == 0 or COL == 0: return 0 vertical = [] horizontal = [] # Find all members home"s position for i in range(ROW): for j in range(COL): if grid[i][j] == 1: vertical.append(i) horizontal.append(j) # Sort positions so we can find most # beneficial point vertical.sort() horizontal.sort() # middle position will always beneficial # for all group members but it will be # sorted which we have alredy done size = len(vertical) // 2 x = vertical[size] y = horizontal[size] # Now find total distance from best meeting # point (x,y) using Manhattan Distance formula distance = 0 for i in range(ROW): for j in range(COL): if grid[i][j] == 1: distance += abs(x - i) + abs(y - j) return distance # Driver Codeif __name__ == "__main__": grid = [[1, 0, 1, 0, 1], [0, 1, 0, 0, 0], [0, 1, 1, 0, 0]] print(minTotalDistance(grid)) # This code is contributed by# sanjeev2552 |
C#
/* C# program to find best meeting point in 2D array*/using System;using System.Collections.Generic; class GFG { static int ROW = 3;static int COL = 5 ; static int minTotalDistance(int [,]grid){ if (ROW == 0 || COL == 0) return 0; List<int> vertical = new List<int>(); List<int> horizontal = new List<int>(); // Find all members home"s position for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (grid[i, j] == 1) { vertical.Add(i); horizontal.Add(j); } } } // Sort positions so we can find most // beneficial point vertical.Sort(); horizontal.Sort(); // middle position will always beneficial // for all group members but it will be // sorted which we have alredy done int size = vertical.Count / 2; int x = vertical[size]; int y = horizontal[size]; // Now find total distance from best meeting // point (x,y) using Manhattan Distance formula int distance = 0; for (int i = 0; i < ROW; i++) for (int j = 0; j < COL; j++) if (grid[i, j] == 1) distance += Math.Abs(x - i) + Math.Abs(y - j); return distance; } // Driver codepublic static void Main(String[] args) { int [,]grid = {{1, 0, 1, 0, 1}, {0, 1, 0, 0, 0}, {0, 1, 1, 0, 0}}; Console.WriteLine(minTotalDistance(grid));}} // This code is contributed by PrinciRaj1992 |
Выход:
11
Сложность времени: O (M * N)
Вспомогательное пространство: O (N)
Эта статья предоставлена Harshit Agrawal . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.