Lintcode 573. Build Post Office II

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.

Code (Java)

public class Solution {
    /**
     * @param grid: a 2D grid
     * @return: An integer
     */
    public int shortestDistance(int[][] grid) {
        // write your code here
        if (grid == null || grid.length == 0) {
            return 0;
        } 

        int nRows = grid.length;
        int nCols = grid[0].length;

        int[][] numVisited = new int[nRows][nCols];
        int[][] minDist = new int[nRows][nCols];
        int numHouses = 0;

        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j] == 1) {
                    numHouses++;
                    bfs(grid, i, j, numVisited, minDist);
                }
            }
        }

        // Find the min minDist
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nRows; i++) {
            for (int j = 0; j < nCols; j++) {
                if (grid[i][j] == 0 && numVisited[i][j] == numHouses) {
                    ans = Math.min(ans, minDist[i][j]);
                }
            }
        }

        if (ans == Integer.MAX_VALUE) {
            return -1;
        }

        return ans;
    }

    private void bfs(int[][] grid, int x, int y, int[][] numVisited, int[][] minDist) {
        int nRows = grid.length;
        int nCols = grid[0].length;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        Queue<Integer> queue = new LinkedList<>();
        boolean[][] visited = new boolean[nRows][nCols];

        queue.offer(x * nCols + y);
        visited[x][y] = true;

        int distance = 0;
        while (!queue.isEmpty()) {
            distance += 1;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int index = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int nx = index / nCols + dirs[j][0];
                    int ny = index % nCols + dirs[j][1];

                    if (isValid(grid, visited, nx, ny)) {
                        queue.offer(nx * nCols + ny);
                        visited[nx][ny] = true;

                        numVisited[nx][ny] += 1;
                        minDist[nx][ny] += distance;
                    }
                }
            }
        }
    }

    private boolean isValid(int[][] grid, boolean[][] visited, int x, int y) {
        int nRows = grid.length;
        int nCols = grid[0].length;

        return x >= 0 && x < nRows && y >= 0 && y < nCols && !visited[x][y] && grid[x][y] == 0;
    }
}