Problem

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.

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

思路

方法1:从空格出发

• 循环枚举所有的office修建位置的可能性(空格)
• 计算从这个位置出发到达所有房子的距离之和•在所有方案中找到最小的距离和

方法2:从房子出发

• 循环枚举所有的房子的位置
• 从房子出发,计算每个空格到达房子的距离•累加某个空格到达其他所有房子的距离之和•在所有空格中,找到最小距离和

方法1的实现

1. find all the empties and count the number of houses
2. find distance sum of the current empty to all the houses by using bfs
   1. if the house we meet equals the number of houses counted at the very beginning, return sum
   2. otherwise, return -1
3. get min sum

    public final static int EMPTY = 0;
    public final static int HOUSE = 1;
    public final static int WALL = 2;

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

        List<Coordinate> empties = new ArrayList<>();
        int numHouse = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == EMPTY) {
                    empties.add(new Coordinate(i, j));
                } else if (grid[i][j] == HOUSE) {
                    numHouse++;
                }
            }
        }

        int shortest = Integer.MAX_VALUE;
        for (Coordinate em: empties) {
            int curPathSum = bfs(em, grid, numHouse);
            shortest = Math.min(shortest, curPathSum);
        }

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

    private int bfs (Coordinate empty, int[][] grid, int numHouse) {
        int[] deltaX = {0, 0, 1, -1};
        int[] deltaY = {1, -1, 0, 0};

        int m = grid.length;
        int n = grid[0].length;

        Queue<Coordinate> queue = new LinkedList<>();
        boolean[][] hash = new boolean[m][n];

        queue.offer(empty);
        hash[empty.x][empty.y] = true;

        int sum = 0;
        int path = 0;
        int houseMeet = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            path++;
            for (int i = 0; i < size; i++) {
                Coordinate cur = queue.poll();
                for (int j = 0; j < 4; j++) {
                    Coordinate adj = new Coordinate(
                        cur.x + deltaX[j],
                        cur.y + deltaY[j]
                    );

                    if (adj.x < 0 || adj.y < 0 || adj.x >= m || adj.y >= n) {
                        continue;
                    }
                    if (grid[adj.x][adj.y] == WALL) {
                        continue;
                    }

                    if (hash[adj.x][adj.y]) {
                        continue;
                    }

                    if (grid[adj.x][adj.y] == HOUSE) {
                        sum += path;
                        houseMeet++;
                    } else {
                        queue.offer(adj);
                    }
                    hash[adj.x][adj.y] = true;
                }
            }
        }

        if (houseMeet == numHouse) return sum;
        return Integer.MAX_VALUE;
    }
}

class Coordinate {
    int x, y;
    public Coordinate (int x, int y) {
        this.x = x;
        this.y = y;
    }
}