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.

Have you met this question in a real interview?

Yes

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

1. BFS

so this problem has two ways to approach.

   1. to enumerate all empty space and bfs to get the distance to all the houses

   2. to enumerate all houses and bfs to get the distance to all empty points.

here we will assume that the house number should be less than the empty space (otherwise there can rarely be solution). so we pick no. 2. the rest is just to find all houses and bfs to get the distance one by one and go through the empty spaces to get the least sum distance.

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

    class Pair {
        int n;
        int m;
        public Pair(int n, int m) {
            this.n = n;
            this.m = m;
        }
    }


    public int HOUSE = 1;
    public int FREE = 0;
    public int WALL = 2;

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

        //get the list that populated with houses
        ArrayList<Pair> houseList = getHouseList(grid);


        //bfs the sum of all houses to all points in the matrix and get the smallest number
        return getSmallestCount(grid, houseList);

    }


    public ArrayList<Pair> getHouseList(int[][] grid) {
        ArrayList<Pair> ans = new ArrayList<Pair>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == HOUSE) {
                    ans.add(new Pair(i, j));
                }
            }
        }
        return ans;
    }


    public int getSmallestCount(int[][] grid, ArrayList<Pair> houseList) {

        int[][] visitsCount = new int[grid.length][grid[0].length];
        int[][] sumDistance = new int[grid.length][grid[0].length];

        for (Pair house : houseList) {
            bfsToAllPoints(house, grid, visitsCount, sumDistance);    
        }

        int minSum = Integer.MAX_VALUE;
        boolean isFinished = false;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == FREE && visitsCount[i][j] == houseList.size()) {
                    minSum = Math.min(minSum, sumDistance[i][j]);
                    isFinished = true;
                }
            }
        }

        if (isFinished) {
            return minSum;
        }

        return -1;
    }

    public void bfsToAllPoints(Pair house, 
                               int[][] grid, 
                               int[][] visitsCount, 
                               int[][] sumDistance) {

        boolean[][] isVisited = new boolean[grid.length][grid[0].length];
        Queue<Pair> houseQueue = new LinkedList<Pair>();

        houseQueue.offer(house);
        isVisited[house.n][house.m] = true;

        int count = 0;
        while (!houseQueue.isEmpty()) {
            int size = houseQueue.size();
            count++;
            for (int i = 0; i < size; i++) {
                Pair cur = houseQueue.poll();
                for (int j = 0; j < 4; j++) {
                    Pair neighbor = new Pair(
                            cur.n + deltaN[j],
                            cur.m + deltaM[j]
                        );

                    if (!isInbound(grid, neighbor.n, neighbor.m)) {
                        continue;
                    }

                    if (isVisited[neighbor.n][neighbor.m]) {
                        continue;
                    }

                    sumDistance[neighbor.n][neighbor.m] += count;
                    visitsCount[neighbor.n][neighbor.m]++;
                    isVisited[neighbor.n][neighbor.m] = true;
                    houseQueue.offer(neighbor);
                }
            }
        }
    }
    public boolean isInbound(int[][] grid, int n, int m) {
        if (n < 0 || n >= grid.length) {
            return false;
        }

        if (m < 0 || m >= grid[0].length) {
            return false;
        }

        return grid[n][m] == FREE;
    }
}