Approach
Breadth-first search
For Shortest Distance from All Buildings, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 54 lines of Python from the credited upstream file 317.py.
- The implementation visibly relies on sequence storage, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def shortestDistance(self, grid: list[list[int]]) -> int:3 DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0))4 m = len(grid)5 n = len(grid[0])6 nBuildings = sum(a == 1 for row in grid for a in row)7 ans = math.inf8 9 10 dist = [[0] * n for _ in range(m)]11 12 reachCount = [[0] * n for _ in range(m)]13 14 def bfs(row: int, col: int) -> bool:15 q = collections.deque([(row, col)])16 seen = {(row, col)}17 seenBuildings = 118 19 step = 120 while q:21 for _ in range(len(q)):22 i, j = q.popleft()23 for dx, dy in DIRS:24 x = i + dx25 y = j + dy26 if x < 0 or x == m or y < 0 or y == n:27 continue28 if (x, y) in seen:29 continue30 seen.add((x, y))31 if not grid[x][y]:32 dist[x][y] += step33 reachCount[x][y] += 134 q.append((x, y))35 elif grid[x][y] == 1:36 seenBuildings += 137 step += 138 39 40 return seenBuildings == nBuildings41 42 for i in range(m):43 for j in range(n):44 if grid[i][j] == 1: 45 if not bfs(i, j):46 return -147 48 for i in range(m):49 for j in range(n):50 if reachCount[i][j] == nBuildings:51 ans = min(ans, dist[i][j])52 53 return -1 if ans == math.inf else ans54