这两道题算是矩阵搜索题目中比较难的了。

先来看Building Post Office II：
http://www.lintcode.com/en/problem/build-post-office-ii/#

该题有如下几个要点需要记：
一，建立一个struct来记录当前点的lvl (层数)，这样可以省掉一个矩阵。
二，先将house存到一个数组里，然后遍历这个数组。
三，如何判断该点是否可以reach所有的house？建立一个count二维数组，针对每一点。当遍历到这点时，count[i][j]++, 最后看count[i][j] 是否等于house 数组的size

class Solution {
public:
    /**
     * @param grid a 2D grid
     * @return an integer
     */
     struct Point{
        int row_idx, col_idx;
        int lvl;
        Point(int r, int c, int l):row_idx(r), col_idx(c), lvl(l){}
     };
    int shortestDistance(vector<vector<int>>& grid) {
        // Write your code here
        if(grid.empty() || grid[0].empty()) return 0;
        int row = grid.size(), col = grid[0].size();
        
        vector<Point> houses;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j] == 1){
                    houses.push_back(Point(i, j, 0));
                }
            }
        }
        vector<vector<int>> distance(row, vector<int>(col, 0));
        vector<vector<int>> reach(row, vector<int>(col, 0));
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for(int i=0; i<houses.size(); i++){
            queue<Point> q;
            vector<vector<bool>> visited(row, vector<bool>(col, false));
            q.push(houses[i]);
            while(!q.empty()){
                Point cur = q.front(); q.pop();
                int lvl = cur.lvl;
                for(auto it : directions){
                    int x = cur.row_idx+it.first, y = cur.col_idx+it.second;
                    if(x<0 || x>=row || y<0 || y>=col || visited[x][y] || grid[x][y] != 0) continue;
                    distance[x][y] += lvl+1;
                    reach[x][y]++;
                    visited[x][y] = true;
                    q.push(Point(x, y, lvl+1));
                }
            }
        }
        int ret = INT_MAX;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j] == 0 && reach[i][j] == houses.size()){
                    ret = min(ret, distance[i][j]);
                }
            }
        }
        return ret == INT_MAX ? -1 : ret;
    }
};

再来看Building Post Office I：
http://www.lintcode.com/en/problem/build-post-office/

这道题的要点就是distance可以直接用 x1-x2 + y1-y2求得，所以并不用搜索。做法还是先把所有房子存在一个数组里，然后对于每一个点，遍历房子数组，求total distance即可。

class Solution {
public:
    /**
     * @param grid a 2D grid
     * @return an integer
     */
    int shortestDistance(vector<vector<int>>& grid) {
        // Write your code here
        if(grid.empty() || grid[0].empty()) return 0;
        int row = grid.size(), col = grid[0].size();
        
        vector<pair<int, int>> houses;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j] == 1){
                    houses.push_back({i, j});
                }
            }
        }
        int ret = INT_MAX;
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j] == 0){
                    int dis = 0;
                    for(int k=0; k<houses.size(); k++){
                        dis += calculate(i, j, houses[k]);
                    }
                    ret = min(ret, dis);
                }
            }
        }
        return ret;
    }
    
    int calculate(int i, int j, pair<int, int> p){
        return abs(i-p.first) + abs(j-p.second);
    }
};

这道题更为优化的解法是从中心（x_median, y_median），一圈一圈向外搜索，找到存在最小值的点即停止。参考：https://zhengyang2015.gitbooks.io/lintcode/build_post_office_573.html