317. Shortest Distance from All Buildings

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:

To find the shortest distance from an empty land to all buildings, we can use BFS for each empty land  and find the minimum.

However, it is too slow.

Instead, we can use BFS from each building and find all distances to all empty lands and calculate the minimum.

We use two auxiliary array to store the aggregate distances to each point, and the number of times each point has been reached.

To calculate the minimum, we first check if the times to reach a point is exactly the number of buildings.



Code:

public class Solution {
    class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public int m;
    public int n;
    public int[][]grid;

    public int shortestDistance(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        
        List<Point> houses = getPoints(1);
        int[][] times = new int[m][n];
        int[][] dist = new int[m][n];
        for (Point house : houses) {
            bfs(house, dist, times);
        }
        
        List<Point> lands = getPoints(0);
        int min = Integer.MAX_VALUE;
        for (Point land : lands) {
            if (times[land.x][land.y] == houses.size()) {
                min = Math.min(min, dist[land.x][land.y]);
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    
    public void bfs(Point house, int[][] dist, int[][] times) {
        Queue<Point> queue = new LinkedList<>();
        boolean[][] hash = new boolean[m][n];
        queue.offer(house);
        hash[house.x][house.y] = true;
        
        int[] k = {1, 0, -1, 0, 1};
        int step = 0;
        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                Point pt = queue.poll();
                for (int i = 0; i < 4; i++) {
                    Point nei = new Point(
                        pt.x + k[i], 
                        pt.y + k[i + 1]
                    );
                    if (!inBound(nei)) {
                        continue;
                    }
                    if (hash[nei.x][nei.y]) {
                        continue;
                    }
                    queue.offer(nei);
                    hash[nei.x][nei.y] = true;
                    times[nei.x][nei.y]++;
                    dist[nei.x][nei.y] += step;
                }
            }
        }
    }
    
    public List<Point> getPoints(int type) {
        List<Point> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == type) {
                    list.add(new Point(i, j));
                }
            }
        }
        return list;
    }
    
    public boolean inBound(Point pt) {
        if (pt.x < 0 || pt.x >= m || pt.y < 0 || pt.y >= n) {
            return false;
        }
        return grid[pt.x][pt.y] == 0;
    }
}