You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

Each 0 marks an empty land which you can pass by freely. Each 1 marks a building which you cannot pass through. Each 2 marks an obstacle which you cannot pass through. For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note: There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Solution

public class Solution {

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

        // start from each building, maintain a set of visited place, and boundary points
        int[][] dists = new int[m][n];
        int[][] reach = new int[m][n];
        int oneCnt = 0;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    oneCnt++;
                    bfs(grid, i, j, oneCnt, dists, reach);
                }
            }
        }


        int dist = Integer.MAX_VALUE;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(reach[i][j] == oneCnt) {
                    // only consider those positions that are reachable from all houses
                    dist = Integer.min(dist, dists[i][j]);
                }
            }
        }

        return dist == Integer.MAX_VALUE ? -1: dist;
    }

    public int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    public void bfs(int[][] grid, int i, int j, int oneCnt, int[][] dists, int[][] reach) {
        int candid = -oneCnt + 1;
        List<int[]> queue = new ArrayList<int[]>();
        queue.add(new int[]{i, j});

        int step = 1;
        while(!queue.isEmpty()) {
            // level wise iteration
            List<int[]> nextQ = new ArrayList<int[]>();
            for(int[] point: queue) {
                // consider the four directions
                for(int[] dir: dirs) {
                    int[] newP = new int[]{point[0] + dir[0], point[1] + dir[1]};
                    if(newP[0] >= 0 && newP[0] < grid.length
                        && newP[1] >= 0 && newP[1] < grid[0].length 
                        && grid[newP[0]][newP[1]] == candid) {
                        nextQ.add(newP);
                        grid[newP[0]][newP[1]]  -= 1;
                        dists[newP[0]][newP[1]] += step;
                        reach[newP[0]][newP[1]] += 1;
                    }
                }
            }
            queue = nextQ;
            step++;
        }
    }
}