[LeetCode][Search] 296. Best Meeting Point

Problem

More LeetCode Discussions

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

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Solution

先找出所有的1的的坐标，然后枚举所有的格子，计算总距离，选择距离最小的那个。

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<pair<int, int> > points;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1) {
                    pair<int, int> p;
                    p.first = i;
                    p.second = j;
                    points.push_back(p);
                }
            }
        }
        
        int minDist = INT_MAX;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                int totalDist = 0;
                for(int k = 0; k < points.size(); k++) {
                    int dist = abs(i - points[k].first) + abs(j - points[k].second);
                    totalDist += dist;
                }
                minDist = min(minDist, totalDist);
            }
        }
        
        return minDist;
    }
};

LeetCode上更好的解答。从Hint的思路

Try to solve it in one dimension first. How can this solution apply to the two dimension case?

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
        vector<int> x;
        vector<int> y;
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1) {
                    x.push_back(i);
                    y.push_back(j);
                }
            }
        }
        
        int minDist = 0;
        minDist += getMin(x);
        minDist += getMin(y);
        
        return minDist;
    }
    
    int getMin(vector<int> &a) {
        sort(a.begin(), a.end());
        
        int i = 0;
        int j = a.size() - 1;
        int dist = 0;
        while (i < j) {
            dist += a[j] - a[i];
            j--;
            i++;
        }
        
        return dist;
    }
};