一个二维平面网格，每个格子是房子则为1，或者是空地则为0。找到一个空地修建一个物流中转站，使得这个物流中转站到所有的房子的距离之和最小。 能修建，则返回最小的距离和。如果无法修建，则返回 -1。
若范围限制在100*100以内的网格，如何计算出最小的距离和？
当平面网格非常大的情况下，如何避免不必要的计算？
输入描述:
4 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0先输入方阵阶数，然后逐行输入房子和空地的数据，以空格分隔。
输出描述:
8能修建，则返回最小的距离和。如果无法修建，则返回 -1。
【常规思路】
枚举所有为0的点，计算到所有为1的点的曼哈顿距离，然后获得总和最小的点。时间复杂度为
分析曼哈顿距离的计算，可以发现：
- 对于一行y0所有为1的点，其到（x,y）的垂直距离之和为： M*(y-y0) 其中M为这一行1的个数
- 对于一列x0所有为1的点，其到（x,y）的水平距离之和为： M*(x-x0) 其中M为这一列1的个数
因此，可以先遍历一遍，统计每一行、每一列对应1的个数
然后，分析每个可能的位置（0）到这些1的
曼哈顿距离之和=水平距离之和+垂直距离之和
using namespace std;
int main()
{int n;cin>>n; vector<vector<int>> map(n,vector<int>(n,0));//地图vector<int> row(n,0); //row[i]表示第i行的1的数目vector<int> col(n,0); //col[i]表示第i列的1的数目vector<pair<int,int>> arr;for(int i=0;i<n;i++)for(int j=0;j<n;j++){cin>>map[i][j];if(map[i][j]==1){row[i]++;col[j]++; //对应 行 列 上的1的数目增加}else{arr.push_back(pair<int,int>(i,j));// 空地点}}int _min=100000000;for(auto it:arr){int x=it.first;int y=it.second;int ans=0;for(int i=0;i<n;i++){ans+=row[i]*abs(i-x); //第i行所有1到当前(x，y)的垂直距离和ans+=col[i]*abs(i-y); //第i列所有1到当前(x，y)的水平距离和}_min=min(_min,ans);}cout<<_min<<endl;}