317. Shortest Distance from All Buildings

Problem:

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.

Analysis:

Reverse bfs. 

1. Bfs from each 1, calculate distance form current 1 to each 0. 
2. Calculate number of 1s.
3. Keep count of visited time of 0s
4. get the min distance. 

Solution:
Be aware of the situation when there is no empty space for building. Check min value when return. 

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

        int m = grid.length;
        int n = grid[0].length;
        int min = Integer.MAX_VALUE;
        int[][] distance = new int[m][n];
        int[][] visitedCount = new int[m][n];
        int buildingCount = 0;

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    buildingCount++;
                    Queue<int[]> queue = new LinkedList<>();
                    boolean[][] visited = new boolean[m][n];
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                    bfs(grid, queue, distance, visitedCount, visited);
                }
        }
        
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0 &&  visitedCount[i][j] == buildingCount) {
                    min = Math.min(min, distance[i][j]);
                }
        }
        
        return min == Integer.MAX_VALUE ? -1 : min;
    }


    private void bfs(int[][] grid, Queue<int[]> queue, int[][] distance, int[][] visitedCount, boolean[][] visited) {
        int level = 0;
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int m = grid.length;
        int n = grid[0].length;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                for (int[] dir: dirs) {
                    int newx = x + dir[0];
                    int newy = y + dir[1];
                    if (newx < 0 || newx >= m || newy < 0 || newy >= n || grid[newx][newy] != 0 || visited[newx][newy]) 
                        continue;
                
                    queue.offer(new int[]{newx, newy});
                    distance[newx][newy] += level;
                    visited[newx][newy] = true;
                    visitedCount[newx][newy]++;
                }   
            }
            
        }   
    }
    
}