573.Build Post Office II

1.Description(Hard)

Given a 2D grid, each cell is either a wall2, an house1or empty0(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-1if 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

return8, 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.)

2.Code

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

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

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

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

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

//这里加了一个dis参数
class Node{
    public int x,y,dis;
    public Node(int x,int y,int dis){
        this.x=x;
        this.y=y;
        this.dis=dis;
    }
}

public class Solution_573 {
     /**
     * @param grid a 2D grid
     * @return an integer
     */

    public int m,n;
    public int[] deltaX={0,0,1,-1};
    public int[] deltaY={1,-1,0,0};

    public int shortestDistance(int[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0){
            return -1;
        }
        m=grid.length;
        n=grid[0].length; 

        //Find all the house
        ArrayList<Node> house=new ArrayList<Node>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    Node node=new Node(i,j,0);
                    house.add(node);
                }
            }
        }
        int housecount=house.size();
        //distance[i][j][k]为k房子到grid[i][j]上的点的距离
        int[][][] distance=new int[housecount][m][n];
        for(int i=0;i<housecount;i++){
            for(int j=0;j<m;j++){
                Arrays.fill(distance[i][j], Integer.MAX_VALUE);
            }
        }

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

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


    //Use bfs to fill the distance[][][]
    public void findDistance(Node root,int[][][] distance,int k,int[][] grid){

        Queue<Node> queue=new LinkedList<Node>();
        queue.offer(root);
        boolean[][] visited=new boolean[m][n];
        visited[root.x][root.y]=true;

        while(!queue.isEmpty()){

            Node current=queue.poll();
            for(int direction=0;direction<4;direction++){
                int neighborX=current.x+deltaX[direction];
                int neighborY=current.y+deltaY[direction];
                //这里括号里的顺序很重要
                if(neighborX>=0 && neighborX<m && neighborY>=0 && neighborY<n 
                   && grid[neighborX][neighborY]==0 && !visited[neighborX][neighborY]){
                    distance[k][neighborX][neighborY]=current.dis+1;
                    Node neighbor=new Node(neighborX,neighborY,current.dis+1);
                    queue.offer(neighbor);
                    visited[neighborX][neighborY]=true;
                }
            }               
        }    
    }

}