# Python solution 72ms beats 100%, BFS with pruning

• Use `hit` to record how many times a `0` grid has been reached and use `distSum` to record the sum of distance from all `1` grids to this `0` grid. A powerful pruning is that during the BFS we use `count1` to count how many `1` grids we reached. If `count1 < buildings` then we know not all `1` grids are connected are we can return `-1` immediately, which greatly improved speed (beat 100% submissions).

``````def shortestDistance(self, grid):
if not grid or not grid[0]: return -1
M, N, buildings = len(grid), len(grid[0]), sum(val for line in grid for val in line if val == 1)
hit, distSum = [[0] * N for i in range(M)], [[0] * N for i in range(M)]

def BFS(start_x, start_y):
visited = [[False] * N for k in range(M)]
visited[start_x][start_y], count1, queue = True, 1, collections.deque([(start_x, start_y, 0)])
while queue:
x, y, dist = queue.popleft()
for i, j in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= i < M and 0 <= j < N and not visited[i][j]:
visited[i][j] = True
if not grid[i][j]:
queue.append((i, j, dist + 1))
hit[i][j] += 1
distSum[i][j] += dist + 1
elif grid[i][j] == 1:
count1 += 1
return count1 == buildings

for x in range(M):
for y in range(N):
if grid[x][y] == 1:
if not BFS(x, y): return -1
return min([distSum[i][j] for i in range(M) for j in range(N) if not grid[i][j] and hit[i][j] == buildings] or [-1])``````

• ``````def shortestDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
if m: n = len(grid[0])
if not m or not n:
return -1
dist = [[0]*n for i in range(m)]
totalB = 0
for i in range(m):
for j in range(n):
if grid[i][j]==1: totalB+=1
## do BFS from each building, and decrement all empty place for every building visit
## when grid[i][j] == -totalB, it means that grid[i][j] are already visited from all buildings
## and use dist to record distances from buildings
def bfs(i, j, bIndex):
queue = collections.deque([(i, j, 0)])
while queue:
i, j, d = queue.popleft()
for x,y in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
if 0<=x<m and 0<=y<n and grid[x][y]==bIndex:
dist[x][y] += d+1
grid[x][y] -= 1
queue.append((x, y, d+1))

bIndex = 0
for i in range(m):
for j in range(n):
if grid[i][j]==1:
bfs(i, j, bIndex)
bIndex -= 1
res = [dist[i][j] for i in range(m) for j in range(n) if grid[i][j]+totalB==0]
return min(res) if res else -1
``````

• solution based on PO and @StefanPochmann

• Best solution!

• Another BFS clear solution with same idea.
Using matrix to count the sum of distance and number of building have visited this position

``````class Solution(object):
def shortestDistance(self, grid):
if not grid or not grid[0]:
return -1

matrix = [[[0,0] for i in range(len(grid[0]))] for j in range(len(grid))]

cnt = 0    # count how many building we have visited
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
self.bfs([i,j], grid, matrix, cnt)
cnt += 1

res = float('inf')
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j][1]==cnt:
res = min(res, matrix[i][j][0])

return res if res!=float('inf') else -1

def bfs(self, start, grid, matrix, cnt):
q = [(start, 0)]
while q:
tmp = q.pop(0)
po, step = tmp[0], tmp[1]
for dp in [(-1,0), (1,0), (0,1), (0,-1)]:
i, j = po[0]+dp[0], po[1]+dp[1]
# only the position be visited by cnt times will append to queue
if 0<=i<len(grid) and 0<=j<len(grid[0]) and matrix[i][j][1]==cnt and grid[i][j]==0:
matrix[i][j][0] += step+1
matrix[i][j][1] = cnt+1
q.append(([i,j], step+1))
``````

• The idea is great but the code style is really bad

• For the sake a better clarify.

``````import itertools
import Queue

inf_ = (1 << 31) - 1

LAND = 0
BUILDING = 1
WALL = 2

class Solution(object):
def bfs(self, grid, s_i, s_j, total_buildings):
n = len(grid)
m = len(grid[0])
dist = [
[inf_ for j in range(m)]
for i in range(n)
]
dist[s_i][s_j] = 0
que = Queue.Queue()
seen = set((s_i, s_j))
que.put((s_i, s_j))
buildings_seen = {(s_i, s_j)}

while not que.empty():
i, j = que.get()
for d_i, d_j in {(-1, 0), (1, 0), (0, 1), (0, -1)}:
n_i, n_j = i + d_i, j + d_j
if n_i < 0 or n_i >= n or n_j < 0 or n_j >= m:
continue
if (n_i, n_j) in seen:
continue
if grid[n_i][n_j] == BUILDING:
if grid[n_i][n_j] != LAND:
continue
dist[n_i][n_j] = dist[i][j] + 1
que.put((n_i, n_j))
if len(buildings_seen) != total_buildings:
return None
return dist

def shortestDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid or not grid[0]:
return 0
n = len(grid)
m = len(grid[0])
accu_dist = [
[0 for j in range(m)]
for i in range(n)
]
count_reachable = [
[0 for j in range(m)]
for i in range(n)
]

count_building = 0
for i, j in itertools.product(range(n), range(m)):
if grid[i][j] == BUILDING:
count_building += 1

for i, j in itertools.product(range(n), range(m)):
if grid[i][j] != BUILDING:
continue
dist = self.bfs(grid, i, j, count_building)
if not dist:
return -1
for i_, j_ in itertools.product(range(n), range(m)):
if grid[i_][j_] == LAND and dist[i_][j_] != inf_:
accu_dist[i_][j_] += dist[i_][j_]
count_reachable[i_][j_] += 1

ans = inf_
for i, j in itertools.product(range(n), range(m)):
if grid[i][j] == LAND and count_reachable[i][j] == count_building:
ans = min(ans, accu_dist[i][j])
return ans if ans != inf_ else -1

assert Solution().shortestDistance([
[1,0,2,0,1],
[0,0,0,0,0],
[0,0,1,0,0],
]) == 7
``````

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