题目描述

Shopee物流会有很多个中转站。在选址的过程中，会选择离用户最近的地方建一个物流中转站。

假设给你一个二维平面网格，每个格子是房子则为1，或者是空地则为0。找到一个空地修建一个物流中转站，使得这个物流中转站到所有的房子的距离之和最小。 能修建，则返回最小的距离和。如果无法修建，则返回 -1。

若范围限制在100*100以内的网格，如何计算出最小的距离和？

当平面网格非常大的情况下，如何避免不必要的计算？

输入描述

4
0 1 1 0
1 1 0 1
0 0 1 0
0 0 0 0

先输入方阵阶数，然后逐行输入房子和空地的数据，以空格分隔

输出描述

8

解题思路

不考虑暴力法，假设这是一个灰常灰常大的矩阵。

  • 1、矩阵上的每行的的点到其他行上的用户的纵向距离是相同的，每列同理；
  • 2、由1中结论，计算仓库到用户的距离是，可不必重复计算，采用缓存存储计算结果
  • 3、计算距离的复杂度从 降低到 。【暴力法对每个可能
    的位置都会计算距离，假设有个位置可放仓库，那么就需要对另外
    个用户求距离。所以最坏情况下要计算次距离】
  • 4、以下代码还是要遍历所有可能的位置，只是计算距离的次数少了。我们还可以引入等势线的概念：
    首先计算所有用户的重心，然后以此为中心；如果中心可放仓库，那么一定是距离的最小的。否则，到
    下一圈等势线上寻找，直到找到可放仓库的位置则停止算法。不过这个等势线不是很好找，有思路的同
    学可以试一下，能有证明就更完美了。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
using namespace std;

struct Pos{
    int x;
    int y;
    Pos(int x_, int y_): x(x_), y(y_){}
    Pos(): x(0), y(0){}
};

//求某一行(列)到其他所有行(列)的纵(横)向距离
int distance(vector<int>& d, size_t idx){
    int res = 0;
    for(int i = 0; i < idx; ++i) res += d[i] * (idx - i);
    for(int i = idx + 1; i < d.size(); ++i) res += d[i] * (i - idx);
    return res;
}

int shopee(vector<vector<int>>& mat){
    int N = mat.size();
    vector<int> row(N, 0);//计算每一行上的用户数
    vector<int> col(N, N);//计算每一列上的用户数

    //距离缓存-存储某一行(列)到其他所有行(列)的纵(横)向距离
    vector<int> row_d(N, -1);
    vector<int> col_d(N, -1);

    //可放置仓库的位置
    vector<Pos> pos; pos.resize(N << 2);
    //循环求每一行(列)上的用户数
    for(int i = 0; i < N; ++i){
        row[i] = accumulate(mat[i].begin(), mat[i].end(), 0);

        for(int j = 0; j < N; ++j) {
            if(0 == mat[i][j]){
                pos.push_back(Pos(i, j));
                --col[j];
            } 
        }
    }
    if(pos.empty()) return -1;
    //开始求解
    int res = numeric_limits<int>::max();
    for(auto& p: pos){
        //对于大型矩阵，可以提前算好距离存储，避免分支语句
        if(row_d[p.x] < 0) row_d[p.x] = distance(row, p.x);//该位置所在行到其他行的纵向距离不在缓存中，需要计算
        if(col_d[p.y] < 0) col_d[p.y] = distance(col, p.y);//同上
        res = min(res, row_d[p.x] + col_d[p.y]);//比较结果
    }
    return res;
}

int main(){
    int N;
    cin >> N;
    vector<vector<int>> mat(N, vector<int>(N, 0));
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j) cin >> mat[i][j];

    cout << shopee(mat) << endl;
}