Shortest Distance From All Buildings - Leetcode Solution

Problem Statement:

You are given an m x n grid. Each cell of the grid represents a street. The value of each cell is either 0, 1, or 2.

• If a cell contains 0, it means it represents a street that you can traverse through freely.
• If a cell contains 1, it represents a building, and you cannot traverse through it.
• If a cell contains 2, it represents a obstacle, and you cannot traverse through it.

You want to reach the bottom-right corner of the grid (m - 1, n - 1). Your task is to find the shortest distance from all buildings to the bottom-right corner. If it is not possible to reach the bottom-right corner, return -1.

Note that you may not move diagonally.

Example:

Input: [[1,0,2,0,1], [0,0,0,0,0], [0,0,1,0,0]]

Output: 7

Explanation: You can start from top-left corner (0,0) and go to (1,0), (2,0), (2,1), (2,2), (2,3), (1,3), and (0,3) to reach the bottom-right corner. The total distance is 7.

Solution:

To solve this problem, we need to calculate the distance of each building to all the empty cells in the grid. We can then find the cell that has the shortest sum of distances to all the buildings.

We can use BFS (Breadth First Search) to calculate the distance of each building to all the empty cells in the grid. We need to perform BFS starting from each building and record the distance of each empty cell that can be reached from that building.

We can use a 2D array called dist to store the distance of each cell from all the buildings. We initialize all the entries in this array to -1.

We can use a 2D array called reach to store the number of buildings that can reach each empty cell. We initialize all the entries in this array to 0.

We start by iterating through the grid and for each cell that contains a building, we perform BFS to calculate the distance of each empty cell that can be reached from that building.

For BFS, we start with the queue containing the coordinates of the initial building. We mark this cell as visited and set its distance in dist to 0. We then explore its 4 neighbors (left, right, up, down) and if they are empty cells that have not been visited before, we add them to the end of the queue and mark them as visited. We also set their distance in dist to the distance of the initial building plus 1. We increment the value of reach for these empty cells.

After performing BFS for each building, we iterate through the grid again and for each empty cell that can be reached by all the buildings, we add its distance in dist to the sum of distances to all the buildings.

We also keep track of the minimum distance obtained so far, and update it whenever we find a new minimum.

If there are no empty cells that can be reached by all the buildings, we return -1.

The Python code for the solution is given below:

from collections import deque class Solution: def shortestDistance(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) buildings = 0 dist = [[-1]*n for _ in range(m)] reach = [[0]*n for _ in range(m)] for i in range(m): for j in range(n): if grid[i][j] == 1: buildings += 1 queue = deque([(i,j)]) level = 1 while queue: for _ in range(len(queue)): x, y = queue.popleft() for dx, dy in ((-1,0),(1,0),(0,-1),(0,1)): nx, ny = x+dx, y+dy if 0<=nx<m and 0<=ny<n and grid[nx][ny] == 0 and dist[nx][ny] == -1: dist[nx][ny] = level reach[nx][ny] += 1 queue.append((nx,ny)) level += 1 ans = float('inf') for i in range(m): for j in range(n): if grid[i][j] == 0 and reach[i][j] == buildings: ans = min(ans, dist[i][j]) return -1 if ans == float('inf') else ans

Time Complexity: O(kmn), where k is the number of buildings.

Space Complexity: O(m*n).

1