Shortest Distance from All Buildings

Similar Problems:

- Walls and Gates
- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #bfs, #meetingpoint

You want to build a house on an empty land which reaches all buildings in the shortest amount of distance. You can only move up, down, left and right. You are given a 2D grid of values 0, 1 or 2, where:

- Each 0 marks an empty land which you can pass by freely.
- Each 1 marks a building which you cannot pass through.
- Each 2 marks an obstacle which you cannot pass through.

For example, given three buildings at (0,0), (0,4), (2,2), and an obstacle at (0,2):

1 - 0 - 2 - 0 - 1 | | | | | 0 - 0 - 0 - 0 - 0 | | | | | 0 - 0 - 1 - 0 - 0

The point (1,2) is an ideal empty land to build a house, as the total travel distance of 3+3+1=7 is minimal. So return 7.

Note:

There will be at least one building. If it is not possible to build such house according to the above rules, return -1.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution: BFS from buildings

## https://code.dennyzhang.com/shortest-distance-from-all-buildings ## Basic Ideas: bfs ## ## Complexity: Time ?, Space ? class Solution: def shortestDistance(self, grid: List[List[int]]) -> int: n, m = len(grid), len(grid[0]) def bfs(i, j): nonlocal dis seen = set() level = 0 seen.add((i, j)) queue = collections.deque([(i, j)]) while len(queue)>0: level += 1 for _ in range(len(queue)): (x, y) = queue.popleft() for (offsetX, offsetY) in [(1, 0), (-1, 0), (0, 1), (0, -1)]: x2, y2 = x+offsetX, y+offsetY if not (0<=x2<n and 0<=y2<m) or grid[x2][y2] == 2: continue if (x2, y2) in seen: continue seen.add((x2, y2)) if grid[x2][y2] == 0: dis[x2][y2][0] += 1 dis[x2][y2][1] += level queue.append((x2, y2)) res = sys.maxsize cnt = 0 buildings = [] dis = [[[0, 0] for _ in range(m)] for _ in range(n)] for i in range(n): for j in range(m): if grid[i][j] == 1: cnt += 1 buildings.append((i, j)) for (i, j) in buildings: bfs(i, j) for i in range(n): for j in range(m): if grid[i][j] == 0 and dis[i][j][0] == cnt: res = min(res, dis[i][j][1]) return res if res != sys.maxsize else -1

- Solution: BFS from empty lands

## https://code.dennyzhang.com/shortest-distance-from-all-buildings ## Basic Ideas: bfs ## ## ## Complexity: Time ?, Space ? class Solution: def shortestDistance(self, grid: List[List[int]]) -> int: n, m = len(grid), len(grid[0]) def bfs(i, j, cnt): dis = 0 seen = set() level = 0 seen.add((i, j)) queue = collections.deque([(i, j)]) while len(queue)>0: level += 1 for _ in range(len(queue)): (x, y) = queue.popleft() for (offsetX, offsetY) in [(1, 0), (-1, 0), (0, 1), (0, -1)]: x2, y2 = x+offsetX, y+offsetY if not (0<=x2<n and 0<=y2<m) or grid[x2][y2] == 2: continue if (x2, y2) in seen: continue seen.add((x2, y2)) if grid[x2][y2] == 1: dis += level cnt -= 1 else: # empty cell queue.append((x2, y2)) return dis if cnt == 0 else sys.maxsize res = sys.maxsize cnt = 0 empties = [] for i in range(n): for j in range(m): if grid[i][j] == 0: empties.append((i, j)) if grid[i][j] == 1: cnt += 1 for (i, j) in empties: res = min(res, bfs(i, j, cnt)) return res if res != sys.maxsize else -1