Leetcode: Shortest Distance from All Buildings

Leetcode: 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.

Understand the problem:
A BFS problem. Search from each building and calculate the distance to the building. One thing to note is an empty land must be reachable by all buildings. To achieve this, maintain an array of counters. Each time we reach a empty land from a building, increase the counter. Finally, a reachable point must have the counter equaling to the number of buildings. 

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

public class Solution {     public int shortestDistance(int[][] grid) {         if (grid == null || grid.length == 0) {             return 0;         }                   int m = grid.length;         int n = grid[0].length;                   int[][] dist = new int[m][n];         int[][] reach = new int[m][n];         // step 1: BFS and calcualte the min dist from each building         int numBuildings = 0;         for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 if (grid[i][j] == 1) {                     boolean[][] visited = new boolean[m][n];                     Queue<Integer> queue = new LinkedList<>();                     shortestDistanceHelper(i, j, 0, dist, reach, grid, visited, queue);                     numBuildings++;                 }             }         }                   // step 2: caluclate the minimum distance         int minDist = Integer.MAX_VALUE;         for (int i = 0; i < m; i++) {             for (int j = 0; j < n; j++) {                 if (grid[i][j] == 0 && reach[i][j] == numBuildings) {                     minDist = Math.min(minDist, dist[i][j]);                 }             }         }                   return minDist == Integer.MAX_VALUE ? -1 : minDist;     }           private void shortestDistanceHelper(int x, int y, int currDist,                                         int[][] dist, int[][] reach, int[][] grid,                                         boolean[][] visited, Queue<Integer> queue) {         fill(x, y, x, y, currDist, dist, reach, grid, visited, queue);                   int m = grid.length;         int n = grid[0].length;                   while (!queue.isEmpty()) {             int size = queue.size();             currDist++;             for (int sz = 0; sz < size; sz++) {                 int cord = queue.poll();                 int i = cord / n;                 int j = cord % n;                                   fill(x, y, i - 1, j, currDist, dist, reach, grid, visited, queue);                 fill(x, y, i + 1, j, currDist, dist, reach, grid, visited, queue);                 fill(x, y, i, j - 1, currDist, dist, reach, grid, visited, queue);                 fill(x, y, i, j + 1, currDist, dist, reach, grid, visited, queue);             }           }     }           private void fill(int origX, int origY, int x, int y, int currDist,                       int[][] dist, int[][] reach,                        int[][] grid, boolean[][] visited, Queue<Integer> queue) {                   int m = dist.length;         int n = dist[0].length;         if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {             return;         }                   if ((x != origX || y != origY) && grid[x][y] != 0) {             return;         }                   visited[x][y] = true;                   dist[x][y] += currDist;         reach[x][y]++;                   queue.offer(x * n + y);     } }