# Clean BFS python solution with explanation

• ``````import copy
from collections import deque

class Solution(object):
def shortestDistance(self, grid):
"""
the basic idea is to do BFS for all buildings to those empty land(the empty should be reachable by
previous buildings), each BFS we can get the smallest distance from the BFS building to all valid empty land,
we sum the distance from empty land to building up we can get the distance required if we set the house in
the empty land, we return the smallest distance

:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
m, n = len(grid), len(grid[0])
sum_grid = copy.deepcopy(grid)
res = 0
empty_land_val = 0
for i, row in enumerate(grid):
for j, ele in enumerate(row):
if ele == 1:
queue = deque([(i, j)])
dist = copy.deepcopy(grid)
res = float("inf")
# BFS for each building to compute dist this building need to reach valid empty land(
# valid means previous building can also reach this empty land), then add up the dist
while len(queue) > 0:
a, b = queue.pop()
for I, J in (a, b + 1), (a, b - 1), (a + 1, b), (a - 1, b):
if 0 <= I < m and 0 <= J < n and grid[I][J] == empty_land_val:
# compute the empty land smallest dist to the cur building
dist[I][J] = dist[a][b] + 1
# sum up with the dist which this empty land need to reach other building
sum_grid[I][J] += dist[I][J] - 1
queue.appendleft((I, J))
# next round grid[I][J] is the value of empty_land
grid[I][J] -= 1
res = min(res, sum_grid[I][J])
empty_land_val -= 1
# if res doesn't change, this means this building cant reach any valid empty land, so return -1
if res == float("inf"):
return -1
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.