https://leetcode.com/problems/best-meeting-point/
因为是曼哈顿距离，所以直接压缩成一维的问题。
一维的grid里，最佳点是中间的点，如果为奇数则为中点，偶数则为中点中的任意一个。
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int m = grid.size();
if(m == 0) return 0;
int n = grid[0].size();
if(n == 0) return 0;
vector<int> y;
vector<int> x;
//init
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
x.push_back(j);
y.push_back(i);
}
}
}
//find median
sort(x.begin(),x.end());
sort(y.begin(),y.end());
int num = x.size();
int mx = x[num/2];
int my = y[num/2];
//calculate distance
int res = 0;
for(int i = 0; i < num; i++) {
int d = abs(x[i] - mx) + abs(y[i] - my);
res += d;
}
return res;
}
};