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.

Have you met this question in a real interview? YesProblem Correction

Example

Example 1

Input: [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]
Output: 7
Explanation:
In this example, there are 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.

Example 2

Input: [[1,0],[0,0]]
Output: 1
In this example, there is one buildings at (0,0).
1 - 0
|   |
0 - 0
The point (1,0) or (0,1) is an ideal empty land to build a house, as the total travel distance of 1 is minimal. So return 1.

public class Solution {
    static class Pair {
        int distSum = 0, buildings = 0;
    }

    public int shortestDistance(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int totalBuildings = 0;
        Pair dist[][] = new Pair[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                dist[i][j] = new Pair();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) {
                    BFS(grid, i, j, dist, m, n);
                    totalBuildings++;
                }
        int minDist = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0 && dist[i][j].buildings == totalBuildings)
                    minDist = Math.min(minDist, dist[i][j].distSum);
        return minDist;
    }

    public void BFS(int[][] grid, int x, int y, Pair[][] dist, int m, int n) {
        int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        q.add(new int[] { x, y });
        int count = 1;
        while (q.size() != 0) {
            int size = q.size();
            while (size-- > 0) {
                int[] node = q.poll();
                for (int i = 0; i < 4; i++) {
                    int newX = node[0] + dir[i][0];
                    int newY = node[1] + dir[i][1];
                    if (newX >= 0 && newX < grid.length && newY >= 0 && newY < grid[newX].length
                            && grid[newX][newY] == 0 && !visited[newX][newY]) {
                        visited[newX][newY] = true;
                        dist[newX][newY].distSum += count;
                        dist[newX][newY].buildings++;
                        q.add(new int[] { newX, newY });
                    }
                }
            }
            count++;
        }
    }
}