shortest distance from all buildings

🏠

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

 1 from collections import defaultdict as dd
 2 
 3 
 4 class Solution:
 5     def shortestDistance(self, M):
 6         def print_m(M):
 7             for m in M:
 8                 print(m)
 9             print("-" * 20)
10 
11         H = set(
12             [(i, j) for i in range(len(M)) for j in range(len(M[i])) if M[i][j] == 1]
13         )
14         dist, visited, Q = dd(int), dd(set), set()
15 
16         for hi, hj in H:
17             Q.add((hi, hj, hi, hj))
18             visited[(hi, hj)].add((hi, hj))
19 
20         distances = []
21         while Q:
22             print_m(M)
23             next_q = set()
24             for hi, hj, i, j in Q:
25                 for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
26                     v_bounds = ni >= 0 and ni < len(M)
27                     h_bounds = nj >= 0 and nj < len(M[0])
28                     in_bounds = v_bounds and h_bounds
29                     if in_bounds:
30                         was_visited = (ni, nj) in visited[(hi, hj)]
31                         blocked = M[ni][nj] == 2
32                         house = M[ni][nj] == 1
33                         if in_bounds and not (was_visited or blocked or house):
34                             M[ni][nj] -= 1
35                             dist[(hi, hj, ni, nj)] = dist[(hi, hj, i, j)] + 1
36                             if M[ni][nj] == -len(H):
37                                 # print_m(M)
38                                 distances.append(
39                                     sum(dist[(a, b, ni, nj)] for a, b in H)
40                                 )
41                             visited[(hi, hj)].add((ni, nj))
42                             next_q.add((hi, hj, ni, nj))
43             Q = next_q
44         if distances:
45             return min(distances)
46         return -1
47 
48 
49 s = Solution().shortestDistance(
50     [
51         [1, 1, 1, 1, 1, 1, 1, 0],
52         [0, 0, 0, 0, 0, 0, 0, 1],
53         [1, 1, 1, 1, 1, 1, 0, 1],
54         [1, 0, 0, 0, 0, 1, 0, 1],
55         [1, 0, 1, 1, 0, 1, 0, 1],
56         [1, 0, 1, 0, 0, 1, 0, 1],
57         [1, 0, 1, 1, 1, 1, 0, 1],
58         [1, 0, 0, 0, 0, 0, 0, 1],
59         [0, 1, 1, 1, 1, 1, 1, 0],
60     ]
61 )
62 print(s)