A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
Example:
Input:
1 - 0 - 0 - 0 - 1
Output: 6
Brute force method:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
int minTotalDistance(vector <vector <int >>& grid ) { vector <pair<int , int >> homes; int rows = grid .size (); int cols = grid [0 ].size (); for (int i = 0 ; i < rows; i++){ for (int j = 0 ; j < cols; j++){ if (grid [i][j] == 1 ) homes.push_back(make_pair(i, j)); } } int res = INT_MAX; for (int i = 0 ; i < rows; i++){ for (int j = 0 ; j < cols; j++){ res = min (res, distance(i, j, homes)); } } return res; } int distance(int i, int j, vector <pair<int , int >> homes){ int sum = 0 ; for (auto h : homes){ sum += (abs (h.first - i) + abs (h.second - j)); } return sum; }
Divide all positions into two groups, and find the middle position between them.
Find x and y of the middle position.
First sort the all xs/ ys
Calculate the sum of distances between all xs and the middle one => Sum(difference of two sides of X(Y) array)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
int minTotalDistance(vector <vector <int >>& grid ) { vector <int > xv; vector <int > yv; for (int i = 0 ; i < grid .size (); i++){ for (int j = 0 ; j < grid [i].size (); j++){ if (grid [i][j] == 1 ){ xv.push_back(i); yv.push_back(j); } } } return getAve(xv) + getAve(yv); } int getAve(vector <int > v){ sort (v.begin(), v.end()); int i = 0 , j = v.size ()-1 ; int res = 0 ; while (i < j){ res += v[j--] - v[i++]; } return res; }
近期评论