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.

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

1 2 3 4 5

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

The shortest distance from any empty land to a building can be calculated by BFS starting from the building in O(mn) time. Therefore the we can calculate distance from all buildings to empty lands by t rounds of BFS starting from each building. t is the total number of buildings.
In each round, we need maintain two values for every empty land: the distance and the accessibility.

• dist[i][j] is the empty land (i, j) to all the buildings.
• grid[i][j] is reused as the accessibility.

What is accessibility? It is the number of buildings that are accessible from the empty land.
In each round of BFS we can maintain these two values. In the end we just need to find the minimum value of dist[i][j] where the accessibility equals t.
One interesting point is that the grid[i][j] can also be used to check if (i, j) is visited in this round. At round k (zero based), those has grid[i][j] == k is the empty land unvisited, visited land will have grid[i][j] == k + 1. Here comes the interesting part. One may ask what if grid[i][j] < k? Answer is we do not go into the lands with grid[i][j] < k as if it is an obstacle. Why can we do that? Because grid[i][j] < k means it is not accessible by at least one of the buildings in previous rounds. Which means not only this land is not our answer, all the lands accessible from (i, j) is also not our answer.
This might be why it runs faster than many implements. The Java version runs in 13 ms.
Java

int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; public int shortestDistance(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dist = new int[m][n]; // Initialize building list and accessibility matrix `grid` List<tuple> buildings = new ArrayList<>(); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) buildings.add(new Tuple(i, j, 0)); grid[i][j] = -grid[i][j]; } // BFS from every building for (int k = 0; k < buildings.size(); ++k) bfs(buildings.get(k), k, dist, grid, m, n); // Find the minimum distance int ans = -1; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans)) ans = dist[i][j]; return ans; }

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

int[] dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1}; public int shortestDistance(int[][] grid) {     int m = grid.length, n = grid[0].length;     int[][] dist = new int[m][n];     // Initialize building list and accessibility matrix `grid`     List buildings = new ArrayList<>();     for (int i = 0; i < m; ++i)         for (int j = 0; j < n; ++j) {             if (grid[i][j] == 1)                 buildings.add(new Tuple(i, j, 0));             grid[i][j] = -grid[i][j];         }     // BFS from every building     for (int k = 0; k < buildings.size(); ++k)         bfs(buildings.get(k), k, dist, grid, m, n);     // Find the minimum distance     int ans = -1;     for (int i = 0; i < m; ++i)         for (int j = 0; j < n; ++j)             if (grid[i][j] == buildings.size() && (ans < 0 || dist[i][j] < ans))                 ans = dist[i][j];     return ans; }

Java – BFS subroutine

public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) { Queue<tuple> q = new ArrayDeque<>(); q.add(root); while (!q.isEmpty()) { Tuple b = q.poll(); dist[b.y][b.x] += b.dist; for (int i = 0; i < 4; ++i) { int x = b.x + dx[i], y = b.y + dy[i]; if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) { grid[y][x] = k + 1; q.offer(new Tuple(y, x, b.dist + 1)); } } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public void bfs(Tuple root, int k, int[][] dist, int[][] grid, int m, int n) {     Queue q = new ArrayDeque<>();     q.add(root);     while (!q.isEmpty()) {         Tuple b = q.poll();         dist[b.y][b.x] += b.dist;         for (int i = 0; i < 4; ++i) {             int x = b.x + dx[i], y = b.y + dy[i];             if (y >= 0 && x >= 0 && y < m && x < n && grid[y][x] == k) {                 grid[y][x] = k + 1;                 q.offer(new Tuple(y, x, b.dist + 1));             }         }     } }

Java – Definition of Tuple

class Tuple { public int y; public int x; public int dist; public Tuple(int y, int x, int dist) { this.y = y; this.x = x; this.dist = dist; } }

1 2 3 4 5 6 7 8 9 10 11

class Tuple {     public int y;     public int x;     public int dist;     public Tuple(int y, int x, int dist) {         this.y = y;         this.x = x;         this.dist = dist;     } }