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:
Input: [[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.

Solution

This question is labeled as "hard" although once you understand the approach it's fairly straight-forward. We begin by performing a BFS starting from each house, while keeping track of the distance from the BFS origin.

Above we are seeing the BFS for each house take place consecutively. In actuality they can all run at once. One a cell has been visited by all N houses, we store the sum of its distances (in white).

The optimal shortest path to each house is the smallest sum. To save space, we store the number of visits in the Matrix itself.

https://leetcode.com/problems/shortest-distance-from-all-buildings/

 1from collections import defaultdict as dd
 2
 3
 4class Solution:
 5    def shortestDistance(self, M):
 6        H = set([(i, j) for i in range(len(M)) for j in range(len(M[i])) if M[i][j] == 1])
 7        dist, visited, Q, blocked, house, distances = dd(int), dd(set), set(), 2, 1, []
 8
 9        for hi, hj in H:
10            Q.add((hi, hj, hi, hj))
11            visited[(hi, hj)].add((hi, hj))
12
13        while Q:
14            next_q = set()
15            for hi, hj, i, j in Q:
16                for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
17                    if (ni >= 0 and ni < len(M)) and (nj >= 0 and nj < len(M[0])):
18                        if not (((ni, nj) in visited[(hi, hj)]) or\
19                         M[ni][nj] is blocked or M[ni][nj] is house):
20                            dist[(hi, hj, ni, nj)] = dist[(hi, hj, i, j)] + 1
21                            M[ni][nj] -= 1
22                            if M[ni][nj] == -len(H):
23                                distances.append(sum(dist[(a, b, ni, nj)] for a, b in H))
24                            visited[(hi, hj)].add((ni, nj))
25                            next_q.add((hi, hj, ni, nj))
26            Q = next_q
27        return min(distances) if distances else -1
28
29M = [
30  [1,0,2,2,0,1],
31  [0,0,0,2,0,0],
32  [0,0,0,2,0,0],
33  [2,2,0,0,0,0],
34  [1,0,0,0,0,0]
35]
36
37s = Solution().shortestDistance(M)
38print(s)