subject

Topic linking
A map of an area is recorded in k Two dimensional array area, among 0 Representing vacant land ,1 Express delivery point .

If you want to choose a place to set up a transfer station , Make the transfer station to each express delivery point 「 Manhattan distance 」 The sum is the smallest . Please return to this Minimum The sum of the distances .

Be careful ：

• Manhattan distance ：distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
• All locations can be used as the set-up points of express transfer stations .

Example 1：

 Input : area = [[0,1,0,0,0],[0,0,0,0,1],[0,0,1,0,0]]
 Output : 5 
 explain :  Three express delivery points are located in (0,1),(1,4)  and  (2,2):
     (1,2)  It is the best transit station location , The total distance is  2 + 2 + 1 = 5.

Example 2:

 Input : area = [[1,1],[1,1]]
 Output : 4
 explain : (0,0)  It is one of the best transfer station sites , The total distance is  0 + 1 + 1 + 2 = 4.

Problem solving

Method 1 ：

Due to Manhattan distance , In fact, it can solve the problem of two dimensions into one dimension
For the following , Select the one indicated by the arrow as the transfer station , Shortest distance

class Solution {
    
public:
    int buildTransferStation(vector<vector<int>>& area) {
    
        vector<int> x;
        vector<int> y;
        for(int i=0;i<area.size();i++){
    
            for(int j=0;j<area[0].size();j++){
    
                if(area[i][j]==1){
    
                    x.push_back(i);
                    y.push_back(j);
                }
            }
        }
        sort(x.begin(),x.end());
        sort(y.begin(),y.end());
        int mid=x.size()/2;
        int res=0;
        for(int xi:x){
    
            res+=abs(xi-x[mid]);
        }
        for(int yi:y){
    
            res+=abs(yi-y[mid]);
        }
        return res;
    }
};