题目
某区域地图记录在 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; } };
