# Two tricks to solve BFS TLE

1. When we do BFS from a point (r, c), if we cannot reach all buildings from this point, mark all reachable 0 from this point to 2.
2. If current depth is larger than or equal to current min distance, just quit.
``````from collections import deque
class Solution(object):
def get_min_dist(self, grid, row, col, count, cur_min):
visited = set([(row, col)])
q = deque([(row, col, 0)])
dx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
dist = 0
while q and count:
r, c, depth = q.popleft()
if grid[r][c] == 1:
count -= 1
dist += depth
if dist >= cur_min:
return cur_min
elif not grid[r][c]:
for dr, dc in dx:
tr, tc = r+dr, c+dc
if tr >= 0 and tc >=0 and tr < len(grid) and tc < len(grid[0]) and grid[tr][tc] < 2 and (tr, tc) not in visited:
q.append((tr, tc, depth + 1))
if count:
for r, c in visited:
if grid[r][c] == 0:
grid[r][c] = 2
return -1
return dist

def shortestDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return -1
n_building = 0
for r in grid:
for g in r:
if g == 1:
n_building += 1
row = len(grid)
col = len(grid[0])
min_dist = float('Inf')

for r in xrange(row):
for c in xrange(col):
if grid[r][c] == 0:
dist = self.get_min_dist(grid, r, c, n_building, min_dist)
if dist == -1:
continue
min_dist = min(dist, min_dist)
return min_dist if min_dist < float('Inf') else -1

`````````

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