Shortest Distance 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.

Example:

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]

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

Output: 7 

Explanation: Given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2),
             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.

Code template:

class Solution {
    public int shortestDistance(int[][] grid) {
        
    }
}

Source: LeetCode 317. Shortest Distance from All Buildings

Explanation:

Essentially, we will start from each building and go towards the rest of the graph using BFS to identify the cost of getting to that building. Once we sum up all the costs to all the buildings, we just need the lowest.

One small point is that, you want to be able to reject points if any building can’t reach it, we do this by keeping track of building paths that we saw each spot in

import java.awt.Point;

class Solution {
    
    private void bfs(int[][] grid, int[][] costs, int[][] seen, Point point) {
        Queue<Pair<Point, Integer>> queue = new LinkedList<>();
        Set<Point> covered = new HashSet<>();
        queue.add(new Pair<>(point, 0));
        while (!queue.isEmpty()) {
            
            Pair<Point, Integer> pair = queue.remove();
            Point p = pair.getKey();
            int cost = pair.getValue();
            if (covered.contains(p)) {
                continue;
            }
            if (grid[p.x][p.y] == 0) seen[p.x][p.y]++;
            covered.add(p);
            for (Point n: getValidNeighbors(grid, p)) {
                queue.add(new Pair<>(n, cost+1));
            }
            costs[p.x][p.y] += cost;
        }
    }
    
    private Set<Point> getValidNeighbors(int[][] grid, Point point) {
        Set<Point> all = new HashSet<>();
        all.add(new Point(point.x, point.y+1));
        all.add(new Point(point.x, point.y-1));
        all.add(new Point(point.x+1, point.y));
        all.add(new Point(point.x-1, point.y));
        return all.stream()
            .filter(p -> p.x >= 0 && p.y >= 0 && p.x < grid.length && p.y < grid[0].length)
            .filter(p -> grid[p.x][p.y] == 0)
            .collect(Collectors.toSet());
    }
    
    public int shortestDistance(int[][] grid) {
        int[][] costs = new int[grid.length][grid[0].length];
        int[][] seen = new int[grid.length][grid[0].length];
        
        boolean[][] done = new boolean[grid.length][grid[0].length];
        Set<Point> houses = new HashSet<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    houses.add(new Point(i, j));
                }
            }
        }
        for (Point house: houses) {
            bfs(grid, costs, seen, house);
        }
        int best = -1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (seen[i][j] == houses.size() && (best == -1 || costs[i][j] < best)) {
                    best = costs[i][j];
                }
            }
        }
        return best;
    }
}

• accepted
• hard