Given a 2D grid, each cell is either an house1or empty0(the number zero, one), find the place to build a post office, the distance that post office to all the house sum is smallest. Return the smallest distance. Return-1if it is not possible.

Notice

• You can pass through house and empty.
• You only build post office on an empty.

Have you met this question in a real interview?

Yes

Example

Given a grid:

0 1 0 0
1 0 1 1
0 1 0 0

return6. (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)

array name
line 58 first index n - 1 , not 0;


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 -1;
        }
        int n = grid.size(), m = grid[0].size();
        int ans = INT_MAX;
        vector<int> costRow(n, 0), numRow(n, 0);
        vector<int> costCol(m, 0), numCol(m, 0);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    ++numRow[i];
                    ++numCol[j];
                }
            }
        }

        calculateCost(costRow, numRow, n);
        calculateCost(costCol, numCol, m);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 0 && ans > costRow[i] + costCol[j]) {
                    ans = costRow[i] + costCol[j];
                }
            }
        }
        if (ans == INT_MAX) {
            return -1;
        }
        return ans;
    }


    void calculateCost(vector<int>& costs, vector<int>& nums, int n) {
        vector<int> prefixSum1(n, 0);
        vector<int> prefixSum2(n, 0);

        prefixSum1[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            prefixSum1[i] = prefixSum1[i - 1] + nums[i];
        }
        prefixSum2[0] = 0;
        for (int i = 1; i < n; ++i) {
            prefixSum2[i] = prefixSum2[i - 1] + prefixSum1[i - 1];
        }

        vector<int> suffixSum1(n, 0);
        vector<int> suffixSum2(n, 0);
        suffixSum1[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suffixSum1[i] = suffixSum1[i + 1] + nums[i];
        }

        suffixSum2[n - 1] = 0;
        for (int i = n - 2; i >= 0; --i) {
            suffixSum2[i] = suffixSum2[i + 1] + suffixSum1[i + 1];
        }

        for (int i = 0; i < n; ++i) {
            costs[i] = prefixSum2[i] + suffixSum2[i];
        }
    }
};