Build Post Office II

• Lintcode : 573 / Leetcode :
• Level : Hard

Problem

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest.

Return the smallest sum of distance. Return -1 if it is not possible.

Example
Example 1:

Input：[[0,1,0,0,0],[1,0,0,2,1],[0,1,0,0,0]]
Output：8
Explanation： Placing a post office at (1,1), the distance that post office to all the house sum is smallest.
Example 2:

Input：[[0,1,0],[1,0,1],[0,1,0]]
Output：4
Explanation： Placing a post office at (1,1), the distance that post office to all the house sum is smallest.
Challenge
Solve this problem within O(n^3) time.

Notice
You cannot pass through wall and house, but can pass through empty.
You only build post office on an empty.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(m n mn)
space: O(m * n)

Answer

class Solution {
public:
    int shortestDistance(vector<vector<int>> &grid) {
        int house = 0;
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> isVisited(m, vector<bool>(n, false));
        vector<vector<int>> stepSum(m, vector<int>(n));
        vector<vector<int>> houseNum(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    bfs(grid, isVisited, stepSum, houseNum, i, j);
                    house += 1;
                }
            }
        }
        int minLen = INT_MAX;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 && houseNum[i][j] == house) {
                    minLen = min(minLen, stepSum[i][j]);
                }
            }
        }
        return minLen == INT_MAX ? -1 : minLen;
    }
    vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    void bfs(vector<vector<int>> &grid, vector<vector<bool>> isVisited, vector<vector<int>> &stepSum, vector<vector<int>> &houseNum, int i, int j) {
        int step = 1;
        queue<vector<int>> q;
        q.push({i, j});
        isVisited[i][j] = true;
        while (!q.empty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                vector<int> pair = q.front(); q.pop();
                for (auto d : dir) {
                    int x = d[0] + pair[0];
                    int y = d[1] + pair[1];
                    if (!isValid(grid, x, y) || isVisited[x][y]) continue;
                    q.push({x, y});
                    isVisited[x][y] = true;
                    stepSum[x][y] += step;
                    houseNum[x][y] += 1;
                }
            }
            step++;
        }
    }
    bool isValid(vector<vector<int>> &grid, int x, int y) {
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] != 0)
            return false;
        return true;
    }
};

tags: BFS

​