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)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

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;     } }