Build Post Office II 574

Question

Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), 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 -1 if it is not possible.

Notice

You cannot pass through wall and house, but can pass through empty.

You only build post office on an empty.

Example

Given a grid:

0 1 0 0 0 1 0 0 2 1 0 1 0 0 0

return 8, You can build at (1,1). (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.

Solution

这道题和I比较类似，但是因为不能穿过wall和house，所以必须用bfs的方法搜索最近距离，而不能直接计算几何距离。

1. 将数组扫描一遍找到所有房子。

2. 为每一个房子建立一个距离矩阵，计算该房子到所有0点的距离。即distance[i][j][k]为k房子到grid[i][j]上的点的距离。计算距离的时候用bfs搜索。

3. 然后遍历图上所有为0的点，查询k张距离矩阵，将所有房子到该点的距离加起来即为在该点建邮局的距离总和。若在查询过程中遇到某个点在某张距离矩阵上的值为无穷大，则说明该点无法到达该房子，直接停止搜索即可。

4. 选3中距离最小的点即可。

代码如下：

public class Solution {
    /**
     * @param grid a 2D grid
     * @return an integer
     */
    class Node{
        int x;
        int y;
        int dis;
        public Node(int x, int y, int dis){
            this.x = x;
            this.y = y;
            this.dis = dis;
        }
    }

    public int shortestDistance(int[][] grid) {
        // Write your code here
        if(grid == null || grid.length == 0 || grid[0].length == 0){
            return -1;
        }

        int n = grid.length;
        int m = grid[0].length;
        ArrayList<Node> house = new ArrayList<Node>();
        //find house position
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 1){
                    house.add(new Node(i, j, 0));
                }
            }
        }
        //no empty place
        int k = house.size();
        if(k == n * m){
            return -1;
        }

        int[][][] distance = new int[k][n][m];
        for(int i = 0; i < k; i++){
            for(int j = 0; j < n; j++){
                Arrays.fill(distance[i][j], Integer.MAX_VALUE);
            }
        }

        for(int i = 0; i < k; i++){
            getDistance(house.get(i), distance, i, grid);
        }

        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j] == 0){
                    int sum = 0;
                    for(int l = 0; l < k; l++){
                        if(distance[l][i][j] == Integer.MAX_VALUE){
                            sum = Integer.MAX_VALUE;
                            break;
                        }
                        sum += distance[l][i][j];
                    }
                    min = Math.min(min, sum);
                }
            }
        }

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

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    //BFS search for shortest path
    private void getDistance(Node curt, int[][][] distance, int k, int[][] grid){
        int n = grid.length;
        int m = grid[0].length;
        Queue<Node> queue = new LinkedList<Node>();
        boolean[][] visited = new boolean[n][m];
        queue.offer(curt);
        visited[curt.x][curt.y] = true;

        while(!queue.isEmpty()){
            Node now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];
                if(nextX >= 0 && nextX < n && nextY >= 0 && nextY < m && grid[nextX][nextY] == 0 && !visited[nextX][nextY]){
                    distance[k][nextX][nextY] = now.dis + 1;
                    queue.add(new Node(nextX, nextY, now.dis + 1));
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
}