题目

题目连接
某区域地图记录在 k 二维数组 area，其中 0 表示空地，1 表示快递分发点。

若希望选取一个地点设立中转站，使得中转站至各快递分发点的「曼哈顿距离」总和最小。请返回这个 最小 的距离总和。

注意：

• 曼哈顿距离：distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
• 所有位置均可作为快递中转站的设立点。

示例 1：

输入: area = [[0,1,0,0,0],[0,0,0,0,1],[0,0,1,0,0]]
输出: 5 
解释: 三个快递分发点分别位于(0,1)，(1,4) 和 (2,2):
     (1,2) 是最佳的中转站选址，总距离为 2 + 2 + 1 = 5。

示例 2:

输入: area = [[1,1],[1,1]]
输出: 4
解释: (0,0) 是最佳的中转站选址之一，总距离为 0 + 1 + 1 + 2 = 4。

解题

方法一：

由于是曼哈顿距离，其实可以可以化解二维为一维的问题
对于下图中，选取箭头所指的选为中转站，距离最短

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;
    }
};

最后

以上就是勤奋灯泡为你收集整理的leetcode-zj-future03：快递中转站选址题目解题的全部内容，希望文章能够帮你解决leetcode-zj-future03：快递中转站选址题目解题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。